CODEWITHSUNDEEP
haskelllist-comprehension
user452306
user452306

Reputation: 179

Why is 1:[[]] equal to (1:[]):[]?

As title says, I'm not fully grasping how haskell interprets 

1:[[]]

Why does it seem to do(1:[]):[] ?

E: I got this thought from:

part'::[a] -> [[a]]
part' [] = [[]]
part' (x:xs) = p ++ [x:ys | ys <- p]
    where p = part' xs

Specifically from p ++ [x:ys | ys <- p]

E.g. for part'[1]: is my train of thoughts correct ?:

part'[1] = (part'[]) ++ [1:ys | ys <- part'[]]
--> = [[]] ++ [1:[[]]]

Hope this makes it clear.

Upvotes: 1

Views: 173

Answers (3)

Will Ness
Will Ness

Reputation: 71119

Behold, the Lists:

[a,b,c] ++ [d,e,f] =
[a,b] ++ [c,d,e,f] =
[a] ++ [b,c,d,e,f] =
[] ++ [a,b,c,d,e,f] =
a : [b,c,d,e,f] =
a : b : [c,d,e,f] =
a : b : c : [d,e,f] =
a : b : c : d : [e,f] =
a : b : c : d : e : [f] =
a : b : c : d : e : f : [] =
[a,b,c,d,e,f] ++ [] =
[a,b,c,d,e] ++ [f] =
[a,b,c,d] ++ [e,f] =
[a,b,c] ++ [d,e,f]

and list comprehensions:

[[a, 0] | a <- [1,2,3]] =
     [r | a <- [1,2,3], r <- [[a, 0]]] =
            concatMap (\a -> [[a, 0]]) [1,2,3] =
[[1, 0]] ++ [[2, 0]] ++ [[3, 0]] =
[[1, 0],     [2, 0],     [3, 0]]

Upvotes: 0

ruben.moor
ruben.moor

Reputation: 1965

The [] in Haskell can be quite confusing.

The empty brackets [] by themselves are the constructor for an empty list. Usually this is explained by this alternative (isomorphic) list definition, where [] is called Nil and : is called Cons.

data List a
  = Nil
  | Cons a (List a)

Things don't exactly get easier when you consider that any finite list has Nil in the end. It's the only possible way to end the recursion, e.g.:

Cons 3 (Cons 4 (Cons 5 Nil))

or, equivalently:

3 : (4 : (5 : []))

Some confusion comes from this handy syntax, which expresses again the same:

[3, 4, 5]

Now someone might read [] as simply the empty list without any clue about Cons and Nil.

Yet there's more: In type signatures, you encounter things like [Int] or [a] which means List Int or List a, thus the brackets - again - express an entirely different thing.

There's the risk of a false intuition regarding the meaning of the brackets in Haskell and suddenly you have to think hard about the exact meaning of things like [1] and [[1]], or 1:[] and (1:[]):[].

Upvotes: 2

Isaac
Isaac

Reputation: 3616

It seems like you're misunderstanding the [... | ys <- p] syntax. In this case, ys is a stand-in for each element of the list p, not for the whole list. The equational reasoning in the last part of your question should be

part' [1] = (part' []) ++ [1:ys | ys <- p]
-- = [[]] ++ [1:ys | ys <- [[]]]
-- = [[]] ++ [1 : []]
-- = [[], [1]]

Upvotes: 8

Related Questions