CODEWITHSUNDEEP
recursionclojure
Damon Snyder
Damon Snyder

Reputation: 1372

Unroll nesting in recursive map in clojure

I'm having trouble unrolling the nested structure of the results of this function. I think it's performing the traversal correctly but the results are deeply nested.

The function attempts to traverse the list and find all of the possible paths through the list where the numerical distance between adjacent elements is either 1, 2, or 3. For example, to go from the first element 1, to the next element 4 only a step of 3 will work. But, for the next step we can either take 1 from 4 to 5, we can take two from 4 to 6 (skipping 5), or three from 4 to 7 (skipping 5 and 6).

My question is two fold: 1) what can I do to prevent the deep nesting? and 2) is there a different way to structure the code to prevent the deep nesting in the first place?

(def l0 (1 4 5 6 7 10 11 12 15 16 19 22))

(defn next-path-with-step [chain step]
  (let [looking-at (first chain)
        next-path (drop-while (fn [a]
                                (not (= (- a looking-at) step)))
                              chain)]
    (if (empty? next-path)
      nil
      next-path)))

(defn find-chains [chains prefix]
  (if (empty? chains)
    prefix
    (map (fn [chain]
           (let [head (first chain)
                 next-paths (filter #(not (nil? %))
                                    (map (partial next-path-with-step chain) [1 2 3]))]
             (find-chains next-paths (conj prefix head))))
         chains)))

To run it:

(find-chains [l0] [])

I get the following results:

(((((((((((([1 4 5 6 7 10 11 12 15 16 19 22]))))) (((([1 4 5 6 7 10 12 15 16 19 22]))))))) ((((((([1 4 5 7 10 11 12 15 16 19 22]))))) (((([1 4 5 7 10 12 15 16 19 22]))))))) (((((((([1 4 6 7 10 11 12 15 16 19 22]))))) (((([1 4 6 7 10 12 15 16 19 22]))))))) ((((((([1 4 7 10 11 12 15 16 19 22]))))) (((([1 4 7 10 12 15 16 19 22])))))))))

What I'm trying to get are the inner sequences as a list. Something like:

([1 4 5 6 7 10 11 12 15 16 19 22] 
 [1 4 5 6 7 10 12 15 16 19 22] 
 [1 4 5 7 10 11 12 15 16 19 22] 
 [1 4 5 7 10 12 15 16 19 22] 
 [1 4 6 7 10 11 12 15 16 19 22] 
 [1 4 6 7 10 12 15 16 19 22]
 [1 4 7 10 11 12 15 16 19 22] 
 [1 4 7 10 12 15 16 19 22])

Upvotes: 0

Views: 108

Answers (1)

leetwinski
leetwinski

Reputation: 17859

here are the minor changes, that will solve that for you:

(defn find-chains [chains prefix]
  (if (empty? chains)
    [prefix] ;; return chain wrapped in a vector to avoid flattening
    ;; use mapcat instead of map to flatten internal find-chains calls
    (mapcat (fn [chain] 
              (let [head (first chain)
                    next-paths (filter #(not (nil? %))
                                       (map (partial next-path-with-step chain) [1 2 3]))]
                (find-chains next-paths (conj prefix head))))
            chains)))

user> (find-chains [l0] [])

;;=> ([1 4 5 6 7 10 11 12 15 16 19 22]
;;    [1 4 5 6 7 10 12 15 16 19 22]
;;    [1 4 5 7 10 11 12 15 16 19 22]
;;    [1 4 5 7 10 12 15 16 19 22]
;;    [1 4 6 7 10 11 12 15 16 19 22]
;;    [1 4 6 7 10 12 15 16 19 22]
;;    [1 4 7 10 11 12 15 16 19 22]
;;    [1 4 7 10 12 15 16 19 22])

Upvotes: 4

Related Questions