Implementing Sequence-Inference in Clojure using Method of Differences

Question

I read that in Haskell, you could create a sequence like this: [1,3..9] I wrote a version in Clojure, and though I liked programming without state, the space complexity is huge. What would be a more efficient way to do this?

Edit: If you're interested in understanding the solution, you can read my blog post.

Use cases:

(infer-n [1 2] 10)     => [1 2 3 4 5 6 7 8 9 10]
(infer-n [1 4 9] 10)   => [1 4 9 16 25 ... 100]
(infer-range [9 7] 1)  => [9 7 5 3 1]

Code:

(defn diffs
  "(diffs [1 2 5 12 29]) => (1 3 7 17)" 
  [alist]
  (map - (rest alist) alist))

(defn const-diff
  "Returns the diff if it is constant for the seq, else nil.
   Non-strict version." 
  [alist]
  (let [ds (diffs alist)
        curr (first ds)]
    (if (some #(not (= curr %)) ds)
      nil
      curr)))

(defn get-next
  "Returns the next item in the list according to the
   method of differences.
   (get-next [2 4]) => 6"
  [alist]
  (+ (last alist)
     (let [d (const-diff alist)]
       (if (= nil d)
         (get-next (diffs alist))
         d))))

(defn states-of
  "Returns an infinite sequence of states that the
   input sequence can have.
  (states-of [1 3]) => ([1 3]
                        [1 3 5]
                        [1 3 5 7]
                        [1 3 5 7 9]...)"
  [first-state]
  (iterate #(conj % (get-next %)) first-state))

(defn infer-n
  "Returns the first n items from the inferred-list.
   (infer-n [1 4 9] 10) => [1 4 9 16 25 36 49 64 81 100]" 
  [alist n]
  (take n (map first (states-of alist))))

(defn infer-range
  "(infer-range [10 9] 1) => [10 9 8 7 6 5 4 3 2 1]" 
  [alist bound]
  (let [in-range (if (>= bound (last alist))
                    #(<= % bound)
                    #(>= % bound))]
    (last (for [l (states-of alist) :while (in-range (last l))] l))))

Answer 1

Helper

(defn diff [s] (map - (rest s) s))

Infer sequence based on method of finite differences

(defn infer-diff [s]
  (->> (take (count s) (iterate diff s)) 
       (map last) reverse 
       (drop-while zero?) ;optional 
       (iterate (partial reductions +))
       (map last) rest 
       (concat s)))

Examples

(take 10 (infer-diff [1 3]))
;=> (1 3 5 7 9 11 13 15 17 19)

(take 10 (infer-diff [1 4 9]))
;=> (1 4 9 16 25 36 49 64 81 100)

Explanation

(def s (list 1 4 9))

(take (count s) (iterate diff s))
;=> ((1 4 9)
;    ( 3 5 )
;    (  2  ))

(map last *1)
;=> (9 5 2)

(reverse *1)
;=> (2 5 9)

This (2 5 9) slice of the pyramid of successive first differences is all you need to determine the rest of the sequence.

(reductions + *1)
;=> (2 7 16) and the next in the sequence is at the end: 16

(reductions + *1)
;=> (2 9 25) and the next in the sequence is at the end: 25

(reductions + *1)
;=> (2 11 36) and the next in the sequence is at the end: 36

Answer 2

With const-diff? defined, iterate and take already give us nearly everything we need here.

A note: since const-diff? does not return a boolean value, it probably should not have a ? in the name.

 (defn interpolate [pattern]
  (when-let [step (const-diff? pattern)]
    (iterate #(+ step %) (first pattern))))

(defn bounded-interpolate [pattern bound]
  (let [cmp (if (> bound (first pattern)) > <)
        past #(cmp % bound)]
    (take-while (comp not past)
                (interpolate pattern))))

iterate is already lazy, so we don't need to build some other lazy-sequence-like semantics on top of it, and it already uses structural sharing on top of it, so the cost should not be too extreme (and we don't need to build a sequence of sequences to make it store the intermediate useful results - it shares the substructure when applicable automatically).

user> (bounded-interpolate [1 3 5] 21)
(1 3 5 7 9 11 13 15 17 19 21)

user> (take 100 (interpolate [1 3 5]))
(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181 183 185 187 189 191 193 195 197 199)