Any clean way to avoid explicit recursion when creating nested loops?
I was discussing this on the clojure channel, and it seems as though avoiding explicit recursion is the idiomatic thing to do. Is there a better way to define a function that loops over an arbitrary number of sequences in a nested fashion, similar to the 'for' macro, without relying on recursion? This is the current approach, using recursion: (defn nested [ seqs] returns lazy 'for'-like nesting of a seq of seqs. (letfn [(nestrec [prefix [list deeper-lists]] (if deeper-lists (mapcat #(nestrec (conj prefix %) deeper-lists) list) (map #(conj prefix %) list)))] (nestrec [] seqs))) so (nested (range) [:a :b]) returns [[0 :a][0 :b] [1 :a] [1 :b] [2 :a] ... ] -- 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 Note that posts from new members are moderated - please be patient with your first post. 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
Re: Any clean way to avoid explicit recursion when creating nested loops?
That's perfect, thanks! On Sep 30, 4:55 pm, Mark Engelberg mark.engelb...@gmail.com wrote: clojure.contrib.cartesian-product does what your nested function does, but more efficiently, using iteration rather than recursion. -- 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 Note that posts from new members are moderated - please be patient with your first post. 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
Re: Nested loops
Out of simple curiosity I wondered how hard it would be to implement flow control using proxy. I know Rich isn't hot on non-structured programming, but there may be times where this might be useful: (ns flow.return-from (:import (flow IReturnFrom))) (defn create-return-from [value] (proxy [Throwable IReturnFrom] [] (value [ args] value))) (defmacro allow-return-from [form] `(try ~form (catch ~'clojure.proxy.java.lang.Throwable$IReturnFrom e# (.value e# (defmacro return [value] `(throw (create-return-from ~value))) (defn my-loop [count] (dotimes [x count] (if (= x 5) (return x ;; examples (allow-return-from (my-loop 10)) ; - 5 (dotimes [x 5] (allow-return-from (dotimes [y 5] (if (= y 2) (return y) (println x y) In order for the above to work you'll need to compile an interface: ;; compile with the following ;; (binding [*compile-path* /path/to/classes] ;; (compile 'flow.return-from-interface)) (ns flow.return-from-interface) (gen-interface :nameflow.IReturnFrom :methods [[value [] Object]]) Pretty cool. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Re: Nested loops
Hi, Am 05.04.2009 um 06:59 schrieb David Sletten: My example is decidedly non-functional (I don't really like that term...My code works--it does function! :-) ). Maybe one should use non-functional for - well - non-functional code and disfunctional for not working code? I was more curious about the general case, but you guys may be right that nested loops just aren't needed. My experience in the general case: If I found myself in need for a 'break' or 'continue', it would have been better to put the undesired values not in the loop in the first place. For example in the break case: (doseq [x some-thing] (... (when (foo x) (break)) ...) ; hypothetical.. would be (doseq [x (take-while (complement foo) some-thing)] (...)) ; working For continue to skip a value, one can use filter/remove. This probably doesn't help for all cases, but I've yet to find such a case for me. (Maybe a sign my projects aren't very involved at the moment.) Sincerely Meikel smime.p7s Description: S/MIME cryptographic signature
Nested loops
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 -~--~~~~--~~--~--~---
Re: Nested loops
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
Re: Nested loops
I didn't take time to read your post in detail because I'm on my way to bed and my brain has already checked out. However, as I've gotten better at Clojure and functional programming, I find I use loops less and less. I just got done putting the finishing touches on a package to analyse stock charts. Typically, I would have loop inside of loop inside of loop. But now, I use map, filter and reduce all over the place, but not a single loop keyword to be found. Nowadays, I feel like that if I have to use 'loop' in my code, it's a huge red flag that I'm doing something wrong. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Re: Nested loops
On Apr 4, 2009, at 6:18 PM, Mark Triggs wrote: 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)) Mark and Jim, Thanks for your responses. You both make an excellent point about functional code not often needing explicit loops (and even being a sign of design problems). My example is decidedly non-functional (I don't really like that term...My code works--it does function! :-) ). It was kind of a first cut in a more imperative style because I thought it might be more efficient destructively modifying a char array rather than copying lots of substrings. I intended to attempt a more functional version next. I was more curious about the general case, but you guys may be right that nested loops just aren't needed. Your example looks useful, Mark. In fact, for the real program I do want to collect all possible suggestions rather than terminating with the first one. So I'll be dealing with sequences anyway. 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 -~--~~~~--~~--~--~---
