Haskell generic typeclass with list

Question

I have a class defined like this, so that foo takes a generic type and returns an Integer:

class Foo a where
  foo :: a -> Integer

and a couple of instances defined so it will work with Bool and Char types:

instance Foo Bool where
  foo _ = 10

instance Foo Char where
  foo _ = 20

If I now want to add an instance for a list with a generic type, I would want to do something like this:

instance Foo [a] where
  foo (t:ts) = (foo t) + (foo ts)

However, this is wrong. From my current understanding, I would want to assume that Haskell infers the types and does something like this:

foo [False,True] -> foo False + foo True -> 10 + 10 = 20

I've looked at several books and read about polymorphism and typeclasses, including Learn You a Haskell For Great Good! but still can't wrap my head around how to solve this?

Answer 1

You need to say that the list must contain Foo values:

instance Foo a => Foo [a] where
  foo (h:t) = foo h + foo t
  foo [] = 0

You can only call foo h when h is a Foo instance, so you need to qualify the type class for [a] so that it only works for lists of Foo instances.

Otherwise, if, for instance, you had a [Int], foo h would imply that you'd try to call foo on an Int value, but foo isn't defined for that type.

With the above implementation for [a] you get expected results:

Prelude> foo [True,False,True]
30
Prelude> foo [True,False,True,True]
40
Prelude> foo "foo"
60

Answer 2

You forgot the base case:

instance Foo a => Foo [a] where
  foo (t:ts) = foo t + foo ts
  foo [] = 0

Mind that the call foo ts does not mean that we call foo on the second element. We actually call recursively the function we define (the foo in boldface), and this will thus keep calling foo on the elements of the list, until the list is exhausted, in which case the base case foo [] = 0 will be used.

So it will evaluate:

   foo (False : True : [])
-> foo False + foo (True : [])
-> 20 + foo (True : [])
-> 20 + foo True + foo []
-> 20 + 20 + foo []
-> 20 + 20 + 0
-> 20 + 20
-> 40
->