1

I'm trying to write a succinct, lazy Pascal's Triangle in Clojure, rotated such that the rows/columns follow the diagonals of the triangle. That is, I want to produce the following lazy-seq of lazy-seqs:

((1 1 1 1 ...)
 (1 2 3 4 ...)
 (1 3 6 10 ...)
 ...
 )

The code I have written is:

(def pascal
  (cons (repeat 1)
        (lazy-seq
          (map #(map + %1 %2)
               (map #(cons 0 %) (rest pascal)))
               pascal
          )))

so that each row is formed by adding a right-shifted version of itself to the previous row. The problem is that it never gets past the first line, since at that point (map #(cons 0 %) (rest pascal))) is empty.

=> (take 5 (map #(take 5 %) pascal))
((1 1 1 1 1))

What's a sensible way to go about solving this? I'm fairly new to programming in Clojure, and the very different way of thinking about a problem that it involves, so I'd really appreciate suggestions from anybody more experienced with this.

Micah Elliott
  • 9,600
  • 5
  • 51
  • 54
Luke Hewitt
  • 91
  • 5

2 Answers2

6

Succinct and lazy

(def pascal (iterate (partial reductions +') (repeat 1)))

(map (partial take 5) (take 5 pascal))
;=> ((1 1 1 1 1) 
;    (1 2 3 4 5) 
;    (1 3 6 10 15) 
;    (1 4 10 20 35) 
;    (1 5 15 35 70))

But too lazy?

(take 5 (nth pascal 10000))
;=> StackOverflowError

Try again

(take 5 (nth pascal 10000))
;=> (0)

Uh-oh, start over, and try, try again

(def pascal (iterate (partial reductions +') (repeat 1)))
(count (flatten (map (partial take 5) (take 100000 pascal))))
;=> 500000

Now these are all in your heap

(take 5 (nth pascal 100000))
;=> (1 100001 5000150001 166676666850001 4167083347916875001)
A. Webb
  • 26,227
  • 1
  • 63
  • 95
  • +1. Do you know why the second invocation of `(take 5 (nth pascal 10000))` gives a different result to the first? The `StackOverFlowError` breaks the sequence somehow? Also, you have a `'` symbol after the `+` that I don't think you need. – OpenSauce Mar 12 '13 at 10:51
  • 1
    @OpenSauce Exactly, this demonstrates the invoke only the first time and cache result behavior of a lazy-seq. That which generated this exception won't be called again, and with the exception having been handled by the REPL the bogus result is cached. The +' does automatic promotion to `BigInt` when needed. If I had taken 6 instead of 5, this would have been shown. – A. Webb Mar 12 '13 at 12:02
2

pascal should not be a var but a function that generates infinite seqs.

Check out this question for usage on lazy-seq

BTW, try this:

(defn gennext [s sum]
  (let [newsum (+ (first s) sum)]
    (cons newsum
          (lazy-seq (gennext (rest s) newsum)))))

(defn pascal [s]
  (cons s
        (lazy-seq (pascal (gennext s 0)))))

enter image description here

(pascal (repeat 1)) gives you integer overflow exception but that does mean it produces the infinite seqs. You can use +' to use big integer.

Community
  • 1
  • 1
yeh
  • 1,496
  • 14
  • 35
  • @A. Webb's code is better, he uses reductions which i don't know. – yeh Mar 09 '13 at 16:01
  • Your explanation is probably more helpful to the OP though :). But I'd avoid using `seq` as a binding symbol as it is already a commonly used function. – A. Webb Mar 09 '13 at 16:04