Sequence Reductions again

OK that function to get the beginning sections of a list is bugging me.

A neater way is with a list comprehension: work my way down the sequence with (drop ...) until the end (no more (seq ...)) and use these numbers to (take...) sections from the start of the list:

(defn heads [s]
  (for [n (range) :while (seq (drop n s))]
    (take (inc n) s)))

So if I go

user=> (def x '(1 2 3 4 5 6 7 8))
#'user/x

Then I get the initial sections of increasing length:

user=> (heads x)
((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2 3 4 5 6) (1 2 3 4 5 6 7) (1 2 3 4 5 6 7 8))

And it's lazy - I can pass (range) as an argument:

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

Now I can make the function that does successively greater reductions like so:

(defn myreduce [f s]
  (map #(reduce f %) (heads s)))

For example:

user=> (reduce + x)
36
user=> (myreduce + x)
(1 3 6 10 15 21 28 36)
user=> (reduce * x)
40320
user=> (myreduce * x)
(1 2 6 24 120 720 5040 40320)

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)

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

Greatest Common Divisor

The code that works out the greatest common divisor looks like this:

(fn [x y]
  (cond
    (> x y) (recur (- x y) y)
    (< x y) (recur (x (- y x))
    :else x))

Within a cond construction you don't have to put the pair of forms for a condition and a corresponding action in a list of their own like in Scheme, which saves some typing, so long as you don't lose count. The :else in there is not anything special, it's just convenient in that as a symbol it evaluates to true in a boolean context. And we note the use of the recur function without a loop: in this case control loops back to the start of the enclosing function definition, thereby saving a bit more typing.

Map Construction

Today we want to write a line or two of code that will take a vector of keys and a vector of values and construct a map to link them.  Without using the built-in functions to do this, of course.

Well, the function (assoc m k v) takes a map m and returns the (possibly) large map created by adding the key-value combination of k and v.  So, we can loop through our vectors adding successive elements by pairs to a starting map, which we can initialise as the empty map, denoted {}.

As we do not know that the two vectors are the same length we check both of them and proceed only as long as they both have elements.

So our code looks like this:

(fn [ks vs]
  (loop [m {}, ks ks, vs vs]
    (if (and (seq ks) (seq vs))
      (recur (assoc m (first ks) (first vs)) (rest ks) (rest vs))
      m)))

At the start of the loop the map m that we are building is initialised to {}.  The two identifiers ks and vs represent the vectors of keys and values inside the loop and they are initialised to the values that are passed to the function.  When we recur these work their way through those initial values, to (rest ks) (rest (rest ks)) etc.

A Map Function

A map contains pairs, where the first element is the key and the second element is the attached value: you can set one up with curly brackets, for example:

user=> (def partner {:laurel :hardy, :hardy :laurel, :chaplin nil})
#'user/partner

Now you can look up, say, Laurel's partner:

user=> (get partner :laurel)
:hardy

In our map, Chaplin does not have a partner, so you get this:

user=> (get partner :chaplin)
nil

Of course - we made the value nil when we created the map.  However, if we look up someone who is not in the map, we also get nil:

user=> (get partner :abbott)
nil

The problem (A nil key) today is to write the code that will check for the case where the key really is in the map but the value is nil - - as opposed to the case where the key is not in the map.

We need the function contains?, which asks whether a key is in a map:

user=> (contains? partner :abbott)
false
user=> (contains? partner :chaplin)
true

And we also need the useful fact that nil equals nil.  Therefore the code we want looks like this:

(fn [k m]
  (and
    (contains? m k)
    (= (get m k) nil)))

Re-implement map

This brings us to the question of how we would implement the function map itself.

This is a basic building block that takes a function and a list and returns a list created by applying the given function to each of the elements of the given list. To map f onto a sequence, apply f to the first element and join the result onto whatever you get my mapping f onto the rest of the sequence.  So the obvious implementation looks like this:-

(defn mymap [f x]
  (if (seq x)
    (cons (f (first x)) (mymap f (rest x)))
    '()))

For example, increment a list of numbers:

user=> (mymap inc '(1 2 3 4))
(2 3 4 5)

However, the built-in function map is lazy. That is to say, I can apply it to an unlimited list provided I don't try to take the whole result. For example, recall that the function range without any parameters returns a lazy sequence of integers starting from 0 and going on forever:

user=> (take 10 (range))
(0 1 2 3 4 5 6 7 8 9)

I can still use this as a parameter in map:

user=> (take 10 (map inc (range)))
(1 2 3 4 5 6 7 8 9 10)

But if I do this with my reimplementation we get this:

user=> (take 10 (mymap inc (range)))
StackOverflowError clojure.lang.ChunkedCons.first (ChunkedCons.java:37)

Because the recursion in the function mymap starts work on its input list whether it needs it or not and just keeps going. To avoid this we want to write a lazy version of the map. In Clojure this is easier to do than to understand. I'm guided here by Fogus & Hauser, p 166. We add the macro lazy-seq to our map definition:

(defn mymap2 [f x]
  (lazy-seq
    (if (seq x)
      (cons (f (first x)) (mymap2 f (rest x)))
      '())))

Now this works for limited sequences:

user=> (take 3 (mymap2 inc '(1 2 3 4 5 6)))
(2 3 4)

But it also works for infinite ones:

user=> (take 3 (mymap2 inc (range)))
(1 2 3)

hmm. Pretty neat.

For the purposes of the 4Clojure exercise  we need to code this as an anonymous function that has an internally visible name so that it can call itself - you can add a name into the function definition form that will do this, as so:

(fn my-map [f x]
  (lazy-seq
    (if (seq x)
      (cons (f (first x)) (my-map f (rest x)))
      '())))

Here the name my-map is visible just inside the body of the definition.