CODEWITHSUNDEEP
haskell
hackeryarn
hackeryarn

Reputation: 312

H-99 Problems: #26 Can't Understand The Solution

I am currently working through H-99 Questions after reading Learn You a Haskell. So far I felt like I had a pretty good grasp of the concepts, and I didn't have too much trouble solving or understanding the previous problems. However, this one stumped me and I don't understand the solution.

The problem is:

Generate the combinations of K distinct objects chosen from the N elements of a list

In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.

The solution provided:

import Data.List    

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

The main point of confusion for me is the y variable. according to how tails works it should be getting assigned the entire list at the beginning and then that list will be preppend to ys after it is generate. However, when the function run it return a list of lists no longer than the n value passed in. Could someone please help me understand exactly how this works?

Upvotes: 3

Views: 261

Answers (2)

cdk
cdk

Reputation: 6778

y is not appended to ys. That would involve the (++) :: [a] -> [a] -> [a] operator.

For that matter the types would not match if you tried to append y and ys. y has type a, while ys has type [a].

Rather, y is consed to ys using (:) :: a -> [a] -> [a] (the cons operator).

The length of the returned list is equal to n because combinations recurses from n to 0 so it will produce exactly n inner lists.

Upvotes: 0

chi
chi

Reputation: 116139

Variable y is not bound to the whole xs list. For instance, assume xs=[1,2,3]. Then:

y:xs' is matched against [1,2,3]  ==> y=1 , xs'=[2,3]
y:xs' is matched against [2,3]    ==> y=2 , xs'=[3]
y:xs' is matched against [3]      ==> y=3 , xs'=[]
y:xs' is matched against []       ==> pattern match failure

Note that y is an integer above, while xs' is a list of integers.

The Haskell code can be read a a non-deterministic algorithm, as follows. To generate a combination of n elements from xs, get any tail of xs (i.e., drop any number of elements from the beginning). If the tail is empty, ignore it. Otherwise, let the tail be y:xs', where y is the first element of the tail and xs' the remaining (possibly empty) part. Take y and add it to the combination we are generating (as the first element). Then recursively choose other n-1 arguments from the xs' remaining part, and add those to the combination as well. When n drops to zero, we know there is only one combination, namely the empty combination [], so take that.

Upvotes: 5

Related Questions