[Haskell-beginners] recursively building lists

[Daniel Fischer]

Am Dienstag 08 Dezember 2009 23:34:30 schrieb Torsten Otto:
> Hi!
>
> While trying to implement "words", we ran into the question of how to build
> lists of lists. The trouble boils down to this:
>
> test = []:[]
>
> is no problem, just as
>
> Prelude> []:[]:[]:[]
> [[],[],[]]
>
> works fine. Now trying to put the two together _is_ a problem:
>
> testlist 1 = []:[]
> testlist n = []:(testlist n-1)
>
>     No instance for (Num [[a]])
>       arising from a use of `testlist' at <interactive>:1:0-9
>     Possible fix: add an instance declaration for (Num [[a]])
>     In the expression: testlist 2
>     In the definition of `it': it = testlist 2
>
> Can someone please explain, what is going on here?

Yes. Function application has higher precedence than aritthmetic operations, so the RHS of 
testlist n is parsed as

[] : ( (testlist n) - 1)

So, by the equation for testlist 1, the compiler knows that

testlist :: (Num n) => n -> [[a]]

In the second equation, you try to subtract 1 from a value of type [[a]], that means you 
need a Num instance for that type.

What you want is

testlist n = []:testlist (n-1)

HTH,
Daniel