26 of 99 Haskell Problems - Why does the result contain multiple lists with the same head?
I'm trying to figure out how one of the solutions to problem 26 99 of Haskell problems works . The solution looks like this:
combination :: Int -> [a] -> [[a]]
combination 0 _ = [ [] ]
combination i xs = [ y:ys | y:xs' <- tails xs, ys <- combination (i-1) xs']
I cannot figure out how it is possible that there will be more than one list with the same head. For me, the part y
in y:ys
that will be created on use tails xs
can only be used to compose one list.
Example:
combination 2 [1,2,3]
First we take y
a part of tails xs
that gives us three lists: [1,(not known yet)]
, [2,(not known yet)]
, [3,(not known yet)]
. So how come we get multiple results with 1 as the head?
I also can't figure out why the list [3]
won't be in the result? It will certainly appear as a chapter in one of the lists created tails xs
. I didn't want to raise this issue in a separate question - I hope that's a good thing.
source to share
List matching defines nested loops. Thus, in the definition
combinations n xs =
we can read the code
[ y:ys | y:t <- tails xs, ys <- combinations (n-1) t]
and
for each (y:t) in (tails xs)
for each ys in (combinations (n-1) t)
produce (y:ys) as a new element of the resulting list
In other words, select n
items from the list - select some item and n-1
items after it in the list.
The non-deterministic nature of this definition is presented by listing all possible solutions. We n-1
only select items to the right of the item to only create solutions that are unique when swapped.
Let's take xs = [1,2,3]
as an example. What produces tails [1,2,3]
?
This is [[1,2,3], [2,3], [3], []]
, of course. Now what is the equivalent
[ r | r <- [[1,2,3], [2,3], [3], []] ]
This means that r
, taken from this list, it sequentially takes the values of its elements. r
is an irrefutable figure; (y:t)
is a rebuttable pattern, that is, it will not match an element []
:
[ (y,t) | (y:t) <- tails [1,2,3]]
=> [(1,[2,3]), (2,[3]), (3,[])]
So, you see, t
it is not "unknown" yet. It is known that this is only the tail of this list. And when it y
matches 3, it t
matches []
.
Besides,
[ (y,q) | (y:t) <- tails [1,2,3], q <- [10,20]]
=> [(1,10), (1,20), (2,10), (2,20), (3,10), (3,20)]
This illustrates your first question quite clearly: for each pattern, the matches are (y:t)
q
derived from [10,20]
, i.e. it also takes the values in the list (here [10,20]
) sequentially, for each y
, as in a nested loop.
For your example combinations 2 [1,2,3]
, we have
combinations 2 [1,2,3]
=
for each (y,t) in [ (1,[2,3]), (2,[3]), (3,[]) ]
for each ys in (combinations 1 t)
produce (y:ys)
=
for y = 1, t = [2,3]
for each ys in (combinations 1 [2,3]) produce (1:ys) , and then
for y = 2, t = [3]
for each ys in (combinations 1 [3]) produce (2:ys) , and then
for y = 3, t = []
for each ys in (combinations 1 []) produce (3:ys)
combinations 1 []
[]
, because it tails []
is [[]]
, and pattern matching (y:t)
with []
as part of the generator (y:t) <- [[]]
will fail; so no solutions will be generated by the third linefor
(which would have 3
solutions in the puzzle), because there are no elements in its right to select the second element, since we need to select 2 elements altogether, 3 really participates in the tails of other solutions, as well as it should).
The second line for
is obviously produces only one solution [2,3]
. What does the first line produce for
?
for each ys in (combinations 1 [2,3]) produce (1:ys)
combinations 1
takes only one element, so it creates [2]
and [3]
; so the first line for
creates two solutions: [1,2]
and [1,3]
. Or in more detail,
combinations 1 [2,3]
=
for y = 2, t = [3]
for each ys in (combinations 0 [3]) produce (2:ys) , and then
for y = 3, t = []
for each ys in (combinations 0 []) produce (3:ys)
and combinations 0
always creates a single solution, which is an empty list (one list with an empty list as its only item [ [] ]
, representing a solution to select 0 items from the list).
Thus, a list of three solutions is returned [[1,2], [1,3], [2,3]]
.
source to share
The main thing to notice here is the recursive nature of the problem.
How can we select i
items from a list?
- If the list is empty, then there are no combinations. So this is not an interesting case.
- If the list is not empty, we can either select the first element for our combination, or not
- If we select it, we still have to select items
i-1
from the rest of the list - If we didn't select it, we still need to select
i
items from the rest of the list
- If we select it, we still have to select items
Doing:
[ y:ys | y:xs' <- tails xs, ys <- combination (i-1) xs']
- Look at all the tails
xs
, that is, look at all the possibilities for choosing the first element for our combinationi
. - Select this first element as described above, we now have elements
i-1
, so we need to contact this element with combinations of elementsi-1
with the rest of the elements.
source to share