[Haskell-cafe] Help with generalizing function
Chaddaï Fouché
chaddai.fouche at gmail.com
Wed Jun 25 05:55:13 EDT 2008
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ï
More information about the Haskell-Cafe
mailing list