CODEWITHSUNDEEP
listhaskelllist-comprehension
Joao Bregunci
Joao Bregunci

Reputation: 169

Beginner doubts on List Comprehension Haskell

I am currently doing the 99 Haskell problems that are on the Wiki. Having said that, I was doing the problem number 26 that requires a program that can write all the combinations with n elements in a given set. I did my implementation with plenty of functions and the program seems correct. But my questions arise not from this, but from one of the solutions of the Haskell Wiki

combinations :: Int -> [a] -> [[a]]
combinations 0 _  = [ [] ]
combinations n xs = [ y:ys | y:xs' <- tails xs
                           , ys <- combinations (n-1) xs']

I understood that y:xs is resolved for every list that is given by function tails, resulting in lists of possible values, but I can't understand how the ys value are made so that y:ys give me all the correct solutions.

And another more important question that I have is why these two expressions have diferent results?

[xs | y:xs <- tails [1,2,3]]
[[2,3],[3],[]]

[xs | y:xs <- tails [1,2,3], z <- xs]
[[2,3],[2,3],[3]]

They may not have any practical use, but they demonstrated for me a Haskell beginner, a very strange behaviour. Why applying z <- xs change the value of xs?

Upvotes: 3

Views: 141

Answers (2)

Zeta
Zeta

Reputation: 105975

They have different results due to the comprehension desugaring rules. If we have

[ expression | a <- as, b <- bs ]

then we will get

concatMap (\a -> concatMap (\b -> [expression]) bs) as

Even if b isn't used in expression, we will still end up with more elements. For example concatMap (const [1]) [1..10] will lead to replicate 10 1. So if you add another list in your comprehension you change the number of concatMap and therefore also the number of outputs (unless the list contained exactly one element):

[a | a <- [1..10]]             -- results in [1..10]
[a | a <- [1..10], _ <- [1,2]] -- results in [1,1,2,2,3,3,4,4,...,9,9,10,10]
[a | _ <- [1,2], a <- [1..10]] -- results in [1..10] ++ [1..10]

Upvotes: 3

chi
chi

Reputation: 116174

The code

combinations n xs = [ y:ys | y:xs' <- tails xs
                           , ys <- combinations (n-1) xs']

reads as: to choose n elements from xs, choose any y in xs, and name the tail of elements coming after y as xs'. Then recursively choose n-1 elements from xs', naming any such choice ys. The result is formed by all the y:ys that can be generated in this way.

Convince yourself that this algorithm indeed takes all the possible choices (precisely: all the choices which respect the ordering given by the original list xs).

Note a few corner cases, which are handled correctly. First, inside tails xs we also find the empty tail [], but this is ignored since it is not of the form y:xs'. Then, the tail xs' could be shorter than n-1 elements. In such case ys <- combinations (n-1) xs' will find zero choices for ys, so no "output" will be generated for this xs'.

Finally, about you last question. Consider this example:

[ 42 | x <- [1,2,3 ] ] == [ 42, 42, 42 ]

The value of x does not affect the value of 42, since 42 is constant, but it does affect its multiplicity. This is very similar to the imperative loop for x in [1,2,3]: print(42), which produces its output several times.

Upvotes: 2

Related Questions