How recursion met the base case Haskell

Question

I am trying to understand this piece of code which returns the all possible combinations of [a] passed to it:

-- Infinite list of all combinations for a given value domain
allCombinations :: [a] -> [[a]]
allCombinations []     = [[]]
allCombinations values = [] : concatMap (\w -> map (:w) values)
                                        (allCombinations values)

Here i tried this sample input:

ghci> take 7 (allCombinations [True,False])
[[],[True],[False],[True,True],[False,True],[True,False],[False,False]]

Here it doesn't seems understandable to me which is that how the recursion will eventually stops and will return [ [ ] ], because allCombinations function certainly doesn't have any pointer which moves through the list, on each call and when it meets the base case [ ] it returns [ [ ] ]. According to me It will call allCombinations function infinite and will never stop on its own. Or may be i am missing something?

On the other hand, take only returns the first 7 elements from the final list after all calculation is carried out by going back after completing recursive calls. So actually how recursion met the base case here?

Secondly what is the purpose of concatMap here, here we could also use Map function here just to apply function to the list and inside function we could arrange the list? What is actually concatMap doing here. From definition it concatMap tells us it first map the function then concatenate the lists where as i see we are already doing that inside the function here?

Any valuable input would be appreciated?

Answer 1

Short answer: it will never meet the base case.

However, it does not need to. The base case is most often needed to stop a recursion, however here you want to return an infinite list, so no need to stop it.

On the other hand, this function would break if you try to take more than 1 element of allCombination [] -- have a look at @robin's answer to understand better why. That is the only reason you see a base case here.

The way the main function works is that it starts with an empty list, and then append at the beginning each element in the argument list. (:w) does that recursively. However, this lambda alone would return an infinitely nested list. I.e: [],[[True],[False]],[[[True,True],[True,False] etc. Concatmap removes the outer list at each step, and as it is called recursively this only returns one list of lists at the end. This can be a complicated concept to grasp so look for other example of the use of concatMap and try to understand how they work and why map alone wouldn't be enough.

This obviously only works because of Haskell lazy evaluation. Similarly, you know in a foldr you need to pass it the base case, however when your function is supposed to only take infinite lists, you can have undefined as the base case to make it more clear that finite lists should not be used. For example, foldr f undefined could be used instead of foldr f []

Answer 2

@Lorenzo has already explained the key point - that the recursion in fact never ends, and therefore this generates an infinite list, which you can still take any finite number of elements from because of Haskell's laziness. But I think it will be helpful to give a bit more detail about this particular function and how it works.

Firstly, the [] : at the start of the definition tells you that the first element will always be []. That of course is the one and only way to make a 0-element list from elements of values. The rest of the list is concatMap (\w -> map (:w) values) (allCombinations values).

concatMap f is as you observe simply the composition concat . (map f): it applies the given function to every element of the list, and concatenates the results together. Here the function (\w -> map (:w) values) takes a list, and produces the list of lists given by prepending each element of values to that list. For example, if values == [1,2], then:

(\w -> map (:w) values) [1,2] == [[1,1,2], [2,1,2]]

if we map that function over a list of lists, such as

[[], [1], [2]]

then we get (still with values as [1,2]):

[[[1], [2]], [[1,1], [2,1]], [[1,2], [2,2]]] 

That is of course a list of lists of lists - but then the concat part of concatMap comes to our rescue, flattening the outermost layer, and resulting in a list of lists as follows:

[[1], [2], [1,1], [2,1], [1,2], [2,2]]     

One thing that I hope you might have noticed about this is that the list of lists I started with was not arbitrary. [[], [1], [2]] is the list of all combinations of size 0 or 1 from the starting list [1,2]. This is in fact the first three elements of allCombinations [1,2].

Recall that all we know "for sure" when looking at the definition is that the first element of this list will be []. And the rest of the list is concatMap (\w -> map (:w) [1,2]) (allCombinations [1,2]). The next step is to expand the recursive part of this as [] : concatMap (\w -> map (:w) [1,2]) (allCombinations [1,2]). The outer concatMap then can see that the head of the list it's mapping over is [] - producing a list starting [1], [2] and continuing with the results of appending 1 and then 2 to the other elements - whatever they are. But we've just seen that the next 2 elements are in fact [1] and [2]. We end up with

allCombinations [1,2] == [] : [1] : [2] : concatMap (\w -> map (:w) values) [1,2] (tail (allCombinations [1,2]))

(tail isn't strictly called in the evaluation process, it's done by pattern-matching instead - I'm trying to explain more by words than explicit plodding through equalities).

And looking at that we know the tail is [1] : [2] : concatMap .... The key point is that, at each stage of the process, we know for sure what the first few elements of the list are - and they happen to be all 0-element lists with values taken from values, followed by all 1-element lists with these values, then all 2-element lists, and so on. Once you've got started, the process must continue, because the function passed to concatMap ensures that we just get the lists obtained from taking every list generated so far, and appending each element of values to the front of them.

If you're still confused by this, look up how to compute the Fibonacci numbers in Haskell. The classic way to get an infinite list of all Fibonacci numbers is:

fib = 1 : 1 : zipWith (+) fib (tail fib)

This is a bit easier to understand that the allCombinations example, but relies on essentially the same thing - defining a list purely in terms of itself, but using lazy evaluation to progressively generate as much of the list as you want, according to a simple rule.