Tuesday 28 February 2012

Sequence Reductions

The next puzzle Sequence Reductions is to write a function that is like reduce, but instead of just returning the final value it returns the intermediate values as well in a list. It needs to be lazy and it should allow either two or three arguments.

OK as a preliminary I want a list of all the initial segments of the list, going up to the complete list.  Define function heads:-

(defn heads [s]
  (for [n (range (count s))]
    (take n s)))


try this:

user=> (def s '(3 1 4 1 5 9))
#'user/s
user=> (heads s)
(() (3) (3 1) (3 1 4) (3 1 4 1) (3 1 4 1 5))


No, not right - I want to start from one element not none.  This should be this:

(defn heads [s]
  (for [n (range (count s))]
    (take (inc n) s)))
user=> (heads s)
((3) (3 1) (3 1 4) (3 1 4 1) (3 1 4 1 5) (3 1 4 1 5 9))


That's the list of initial sections of the input list.

No, hang on.  I want the result to be lazy, but there's (count s) in there - this will have to evaluate its argument so it can't be lazy.

I can take 6 from range...

user=> (take 6 (range))
(0 1 2 3 4 5)


But pass this through the function:

user=> (take 6 (heads (range)))

....never returns because it tries to count an infinite list.

OK, different approach.

I want a function that will retain the whole list.  But also I want to step through the list item by item so I know when to stop.  Try a function inside the function, like this:-

(def s '(1 2 3 4 5 6))
(defn heads [s]
  (map (fn [n x] (take (inc n) s))
       (range)
       s))


This does the job of assembling the sub-sections of the list, like this:

user=> (heads s)
((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2 3 4 5 6))


and it's lazy:

user=> (take 4 (heads (range)))
((0) (0 1) (0 1 2) (0 1 2 3))


OK, now to build a multiple reduce function by applying the real reduce function to all these sub-lists from the list:

(defn myreduce [f s]
  (map #(reduce f %)
         (map (fn [n x] (take (inc n) s))
          (range)
          s)))


So we get this:

user=> s
(1 2 3 4 5 6)
user=> (myreduce + s)
(1 3 6 10 15 21)
user=> (myreduce * s)
(1 2 6 24 120 720)


Looks ok.  Also I want to be able to call it with a starting number followed by the rest of the list as an alternative to just the list.  Open up the function so that the assignment to the identifier is separate from the definition so I can use this separately. In the body of the function definition we can have two definitions, one for the parameter list [f s] and one for the list [f x s] where x is a new element to start.  The body of the function for this list just adds the new element to the list and then calls the two-parameter version via the internal identifier this.

(def myreduce
  (fn this
    ([f s]
      (map #(reduce f %)
           (map (fn [n x] (take (inc n) s))
                (range)
                s)))
    ([f x s]
      (this f (cons x s)))))


So does this work?

user=> (myreduce * 10 s)
(10 10 20 60 240 1200 7200)
user=> (myreduce + 10 s)
(10 11 13 16 20 25 31)
user=> (myreduce + (cons 10 s))
(10 11 13 16 20 25 31)

Monday 27 February 2012

Lazy Evaluation

3 . 1 4 1 5 9
Seek that value, line by line:
Slice your logic, chop it fine.

Must you break the silent spell?
Got your answer? Read it well -
Symbols too have lies to tell.

Which is value? Which is sign?
Spill your secret - I keep mine:
2 6 5 3 5 8 9