Hi David,
Quite a few times when I've felt the need for this sort of thing I've
found that laziness comes to the rescue. Would something like this
sort of approach work for you?
(defn possibilities [word pos]
"All variations of `word' with letters from 'a' to 'z' inserted at
`pos'"
(let [[beg end] (split-at pos word)
letters (map char (range (int \a) (inc (int \z))))]
(map #(apply str (concat beg [%] end)) letters)))
(defn all-possibilities [word]
(for [n (range (inc (count word)))
pos (possibilities word n)]
pos))
;; Since all-possibilities produces a lazy seq we don't need short
circuiting anyway...
(some #(binary-search word) (all-possibilities "hello"))
Cheers,
Mark
On Apr 5, 1:26 pm, David Sletten <da...@bosatsu.net> wrote:
> I'm working on a spell checker that attempts to suggest corrections
> from a given dictionary. One of the heuristics is to see if inserting
> a character at each point in the given string results in a recognized
> word. So I have an outer loop that moves across each position in the
> string and an inner loop that tests a-z at that point. In Common Lisp
> I use this:
> (defun word-insertion (s)
> (let ((s1 (make-string (1+ (length s))))) ; Copy the input and
> make room for an extra char
> (setf (subseq s1 1 (length s1)) s)
> (dotimes (i (length s1) nil) ; Outer loop
> (unless (zerop i) (setf (char s1 (1- i)) (char s (1- i))))
> (dotimes (j (1+ (- (char-code #\z) (char-code #\a)))) ;
> Inner loop
> (setf (char s1 i) (code-char (+ j (char-code #\a))))
> (let ((index (binary-search s1))) ; Check in the
> dictionary for a match
> (when index (return-from word-insertion index)))) ))) ;
> Done if match found
>
> The main point is that I can use two DOTIMES forms, one nested inside
> the other, and I can exit either at any point. I actually exit the
> entire function as soon as I find a match via RETURN-FROM.
>
> Clojure has 'dotimes', but from what I understand there is no way to
> exit prematurely?
>
> The obvious alternative is to nest a couple of 'loop' forms:
> (defn g [p q]
> (loop [i 0]
> (if (= i p)
> nil
> (do
> (loop [j 0]
> (if (= j q)
> nil
> (do
> (prn (list i j))
> (recur (inc j)))) )
> (recur (inc i)))) ))
>
> The loop/recur pairs seem to establish outer and inner recursion
> points (I can't really tell from the macro expansion), and this
> function behaves as expected. This approach appears to be equivalent
> to something like this:
> (defn f [p q]
> (letfn [(outer [i]
> (if (= i p)
> nil
> (do
> (inner i 0)
> (outer (inc i)))) )
> (inner [i j]
> (if (= j q)
> nil
> (do
> (prn (list i j))
> (inner i (inc j)))) )]
> (outer 0)))
>
> Again the important thing is that I can terminate the inner loop
> based on my own condition. However, it seems that in the outer loop I
> have to capture the value of the inner loop directly. I can't simply
> leave both loops:
> (defn word-insertion [s]
> (let [s1 (make-array Character/TYPE (inc (count s)))]
> (System/arraycopy (.toCharArray s) 0 s1 1 (count s))
> (loop [i 0]
> (if (= i (count s1))
> nil
> (do
> (when-not (zero? i)
> (aset s1 (dec i) (nth s (dec i))))
> (let [match (loop [j 0]
> (if (= j (inc (- (int \z) (int \a))))
> nil
> (do
> (aset s1 i (char (+ j (int \a))))
> (let [match (binary-search (String. s1))]
> (if match
> match
> (recur (inc j)))) )))]
> (if match
> match
> (recur (inc i)))) )))) )
>
> One other version I considered makes due with a single 'loop', but
> this is pretty convoluted:
> (defn word-insertion [s]
> (let [s1 (make-array Character/TYPE (inc (count s)))]
> (System/arraycopy (.toCharArray s) 0 s1 1 (count s))
> (loop [i 0
> j 0]
> (when (and (not (zero? i))
> (zero? j))
> (aset s1 (dec i) (nth s (dec i))))
> (cond (= i (count s1)) nil
> (= j (inc (- (int \z) (int \a)))) (recur (inc i) 0)
> :else (do
> (aset s1 i (char (+ j (int \a))))
> (let [match (binary-search (String. s1))]
> (if match
> match
> (recur i (inc j)))) )))) )
>
> The one nice thing about this is I can terminate the entire loop and
> return a value in one step. Otherwise the logic is a mess.
>
> Any suggestions out there?
>
> Aloha,
> David Sletten
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
