2008/6/25 leledumbo
Hi, I'm back. I have some troubles understanding your code:
( 1:1:? is never reached. )
Why would 1:1 be reached when we search for lists with a sum of 1 ?? Your derivation is incorrect, when you're reading a list comprehension you must see it as imbricated loops, let's see a correct derivation : findAllAns 2 1 ==> [ x:xs | x <- [0..1], xs <- findAllAns 1 (1 - x) ] ==> concat [ [ 0 : xs | xs <- findAllAns 1 1 ], [ 1 : xs | xs <- findAllAns 1 0 ] ] findAllAns 1 1 ==> [ concat [ [ [ 0 : xs | xs <- findAllAns 0 1 ], [ 1 : xs | xs <- findAllAns 0 0 ] ] ==> concat [ [], [[1]] ] ==> [ [ 1 ] ] In reality, all list comprehensions are translated to ordinary functions under the hood, the translation is the following : [ x:xs | x <- [0..s], xs <- findAllAns (n - 1) (s - x) ] == concatMap (x -> concatMap (\xs -> x : xs) (findAllAns (n - 1) (s - x)) [0..s] which is then easier to derive.
I don't understand why if the last element is [[]] then it's included in the result and not if it's [].
I think with the concatMap above you'll understand better what's going on : "concatMap (\xs -> 0 : xs) (findAllAns 0 1)" returns the empty list because "findAllAns 0 1" is an empty list while "concatMap (\xs -> 1 : xs) (findAllAns 0 0)" returns [[1]] because "findAllAns 0 0" is a list that contains the empty list. But you don't have to think so hard to find the good response, just think of the edge cases logically : faire une somme de 0 avec 0 éléments c'est possible (parce que 0 est l'élément neutre de l'addition), tandis que faire une somme différente de 0 avec 0 éléments est impossible. (The sum of 0 elements is always 0, and the product of 0 elements is always 1) -- Jedaï