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))

Answer 2

According to ClojureDocs

conj

conj clojure.core

(conj coll x)
(conj coll x & xs)

conj[oin]. Returns a new collection with the xs 'added'. (conj nil item) returns (item). The 'addition' may happen at different 'places' depending on the concrete type.

conj accepts the first argument as a collection, which means coll must be a collection type. conj will return a new collection with x added into coll, and the place of x added is depending on the type of coll.

e.g.

> (conj [1] [0])
 [1 [0]] ; See [0] is added into [1] as an element. Instead of returning [1 0], it returns [1 [0]]
> (conj [1] 0)
 [1 0]
> (conj '(1) 0)
 (0 1) ;See the element `0` position is different in each case.

concat

concat clojure.core
(concat)
(concat x)
(concat x y)
(concat x y & zs)

Returns a lazy seq representing the concatenation of the elements in the supplied colls.

concat accepts all the argument as collection types, which is different from conj. concat returns the concatenation of arguments.

e.g.

> (concat [0] [1])
(0 1)
> (concat [0] [[1]])
(0 [1])
> (concat [0] 1) ;See the second argument is not a collection type, thus the function throws an exception.
java.lang.IllegalArgumentException: Don't know how to create ISeq from: java.lang.Long
>  

cons

cons clojure.core 
(cons x seq)

Returns a new seq where x is the first element and seq is the rest.

The doc of cons states clearly how cons would work. The second argument of cons must be a seq.

e.g.

> (cons [1] [0])
([1] 0) ; [1] is the first element and (0) is the rest
> (first (cons [1] [0]))
[1]
> (rest (cons [1] [0]))
(0)
> (cons 1 [0]) ; 1 is the first element and (0) is the rest
(1 0)
> (cons [1] 0) ;the second argument is not a seq, throwing exception
java.lang.IllegalArgumentException: Don't know how to create ISeq from: java.lang.Long

Answer 3

conj on a list adds the element to the front of the list. If you convert the list to a vector it will work.

user=> (conj '(1 2 3) 4)
(4 1 2 3)
user=> (conj [1 2 3] 4)
[1 2 3 4]