[Haskell-cafe] Help with generalizing function

[Chaddaï Fouché]

2008/6/25 leledumbo <leledumbo_cool at yahoo.co.id>:
>
> 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ï