Whats the difference between (concat [x] y) and (cons x y)?

Question

I am stuck at the Pascal's Trapezoid from 4Clojure site, where you need to build a lazy sequence of the trapezoid's numbers.

My first shot was this:

(defn pascal [x]
  (cons x
   (lazy-seq
    (pascal 
     (map +
        (cons 0 x)
        (conj x 0)      
      )))))

Which didn't work:

user=> (take 5 (pascal [1 1]))
([1 1] (1 2 1) (0 2 4 2) (0 0 4 8 4) (0 0 0 8 16 8))

Writing it this way works, however:

(defn pascal2 [x]
  (cons x
   (lazy-seq
    (pascal2
     (map +
        (concat [0] x)
        (concat x [0])      
      )))))

user=> (take 5 (pascal2 [1 1]))
([1 1] (1 2 1) (1 3 3 1) (1 4 6 4 1) (1 5 10 10 5 1))

So, what exactly am I doing wrong here? What is the difference between cons/conj and concat?

Answer 1

As others stated conj inserts the element(s) it receives in a different position depending on the concrete collection type, see this SO question for more detailed information about the difference between conj and cons.

In the first version of your pascal function you are providing a vector as the initial argument so the expression (conj x 0) will insert the 0 at the end of the vector for the computation of the second element in the series, but since map returns a lazy sequence, when the third element is computed the insertion happens at the beginning ((conj (map inc '(0)) 2) ;= (2 1)), which results in wrong elements in the series from then on.

In order to use the cons and conj approach you have to make sure you return a vector by using mapv instead of map.

(defn pascal [x]
  (cons x
   (lazy-seq
    (pascal 
     (mapv +
        (cons 0 x)
        (conj x 0))))))

(take 5 (pascal [1 1]))

;= ([1 1] [1 2 1] [1 3 3 1] [1 4 6 4 1] [1 5 10 10 5 1])

The drawback with mapv is that it is eager so it will compute all members in the pascal element, instead of just holding it back until you actually need them.

On the other hand, when using concat you do ensure you append the element at the end and that everything is lazy, but the append is not done cheaply like with vectors, see here for more information.

Regardless of these factors you can still use cons in both cases, since what it does is what you need in either case (i.e. have an element inserted at the beginning of a collection).

(defn pascal2 [x]
  (cons x
   (lazy-seq
    (pascal2
     (map +
        (cons 0 x) ; Replaced concat with cons
        (concat x [0]))))))

(take 5 (pascal2 [1 1]))

;= ([1 1] (1 2 1) (1 3 3 1) (1 4 6 4 1) (1 5 10 10 5 1))