CODEWITHSUNDEEP
listhaskelllist-comprehensionlazy-evaluation
Arpan Biswas
Arpan Biswas

Reputation: 185

How does haskell create a new list from another list?

Suppose we have a list

x = [1..10]

and we intend to create another list y using this in this manner :

y= [a|a<-x]

So while creating the list y from x, it accesses each element of x( from 1 to 10) and inserts it in y in the same order. As a list in haskell is singly linked list, we can insert a new element only at its head. So first it inserts 1 to [] & we have [1]. Then it inserts 2 to its head & so we have [2,1]. Then it inserts 3 & we have [3,2,1] & so on. So ultimately we should get y as [10,9..1]. But instead we get y as [1..10]. Why is that so?

Upvotes: 3

Views: 3197

Answers (3)

chepner
chepner

Reputation: 530970

It's instructive to look at exactly how list comprehensions desugar to monadic computations, rather than use the intuition for how they work.

[a | a <- [1..3]] == do {a <- [1..3]; return a}   -- desugared comprehension
                  == [1..3] >>= return a          -- desugared do
                  == concat (map return [1..3])   -- definition of >>=
                  == concat [[1], [2], [3]]       -- defintiion of return
                  == [1,2,3]                      -- definition of concat

Upvotes: 4

Chris Taylor
Chris Taylor

Reputation: 47392

The way you are thinking about list comprehensions is not quite correct. When you see a comprehension

y <- [f a | a <- x]

you shouldn't think about the successive result being added to the front of an (initially empty) result list.

Instead, think of each f a being added to the front of the result of running the list comprehension on the rest of x. That is,

[f a | a <- x:xs] == f x : [f a | a <- xs]

This is a recursive approach - by assuming that the result list exists for the tail of the list, you can add the next result to the front of it.

Upvotes: 6

Will Ness
Will Ness

Reputation: 71065

Because it "inserts" them at list's tail (while the list is being built), not head (cf. "tail recursion modulo cons"):

[a | a <- [1..10]]     ==
[a | a <- (1:[2..10])] ==      -- [a | a <- ([1] ++ [2..10])]
1 : [a | a <- [2..10]]         -- [1] ++ [a | a <- [2..10]]

This is because

[a | a <- (xs ++ ys)]  ==  [a | a <- xs] ++ [a | a <- ys]

and

[a | a <- ys]  ==  ys

Upvotes: 6

Related Questions