CODEWITHSUNDEEP
haskellconstructortypeclassmonoids
Ali
Ali

Reputation: 117

Why type constructors can not be used in typeclass definition in haskell?

data LinkedList a = Empty | Cons a (LinkedList a)   deriving (Eq, Show)

instance  Foldable LinkedList where
  foldMap _ Empty  = mempty
  foldMap f (a `Cons` ll) =  LinkedList (f a)  (foldMap f ll)

It seems LinkedList constructor is not in scope? Why?

compiler error:

        Data constructor not in scope: LinkedList :: m -> m -> m
   |        
17 |   foldMap f (a `Cons` ll) =  LinkedList (f a)  (foldMap f ll)
   |                              ^^^^^^^^^^

I searched for a solution and it seems that I should have used 'mappened' instead of constructor. Which is very confusing. I have not defined anywhere any Monoid typeclass.

Can you explain why mappened and not the constructor? And where the Monoid functions mappened and mempty are defined?

Edit ---------------------------------------------------------------------

I made a mistake when I had changed back from mappened. Sorry, but the correct question is this:

instance  Foldable LinkedList where
  foldMap _ Empty  = mempty
  foldMap f (a `Cons` ll) =  Cons (f a)  (foldMap f ll)

the compiler Error:

     • Occurs check: cannot construct the infinite type:
        m ~ LinkedList m
    • In the second argument of ‘Cons’, namely ‘(foldMap f ll)’
      
   |        
17 |   foldMap f (a `Cons` ll) =  Cons (f a)  (foldMap f ll)
   |            

                           ^^^^^^^^^^^^

Why can't I use foldMap recursively? And also where the Monoid functions are defined.

Upvotes: 1

Views: 126

Answers (2)

Robin Zigmond
Robin Zigmond

Reputation: 18259

The compiler error message should contain enough detail for you to figure out what is wrong with your code:

     • Occurs check: cannot construct the infinite type:
        m ~ LinkedList m
    • In the second argument of ‘Cons’, namely ‘(foldMap f ll)’
      
   |        
17 |   foldMap f (a `Cons` ll) =  Cons (f a)  (foldMap f ll)
   |            

                           ^^^^^^^^^^^^

Ignoring the parts about "occurs check" and "infinite type", which I accept may seem a little confusing, it's complaining that foldMap f ll is supposed to have type m when it has actual type LinkedList m, or possibly (as it turns out) the other way round. So let's look at the types ourselves.

It starts with the type of foldMap, which we can easily find in the documentation:

foldMap :: Monoid m => (a -> m) -> t a -> m

this means that foldMap f ll will have type m, for any Monoid m (whichever specific Monoid the caller picked as the return type of the function f).

Meanwhile, f has type a -> m, so f a must have type m - again for the arbitrary Monoid instance picked by f. So when f a is used as the first argument of Cons - Cons (f a) (foldMap f ll) - we can compare to the definition of Cons, which comes from the type definition:

data LinkedList a = Empty | Cons a (LinkedList a)

which tells us that, since f a has type m, Cons (f a) (foldMap f ll) must be supposed to be a value of type LinkedList m. And therefore foldMap f ll must have that same type. (As both of the LinkedList types in the definition are applied to the same type a.)

And this gives us the problem reported by the compiler - foldMap f ll must be both of type m and of type LinkedList m.

(Aside: GHC doesn't in fact give up at that point, it assumes the types actually are equal to each other and sees where that leads. But here it simply leads to an infinite regress: the value concerned must have type m which equals LinkedList m which equals LinkedList (LinkedList m) and so on. Haskell is fine with infinite regress like this in value definitions but doesn't allow it for types - hence "cannot construct the infinite type".)

How do we fix this error and get a correct foldMap definition? You had absolutely the right idea in trying to combine f a and foldMap f ll in computing foldMap f (Cons a ll). Both of those are of type m, for the particular (arbitrary) Monoid targeted by the f. We can't necessarily combine those with a "normal function" like, say, (+), because we don't know what type m is - it won't necessarily be a numeric type, or whatever. But the one thing we do know is that it is an instance of Monoid - and therefore that we can indeed combine any two such values with the Monoid method mappend. And in fact, we can't really do much else, because we know nothing about the type m here except that it's an instance of Monoid - and therefore has mappend :: m -> m -> m (and mempty :: m) available.

So there's only one way to combine these values into the correct definition, which is:

foldMap f (Cons a ll) = mappend (f a) (foldMap f ll)

There is no Cons (or Empty) to be seen on the right - if this puzzles you, consider that foldMap takes a LinkedList as input (in this particular case that's the Cons a ll argument), but it doesn't output a LinkedList, it instead outputs a value in the arbitrarily-chosen Monoid m.

I hope this helps, but it may be a little hard to follow if you've not come across Monoids much before - especially if you're trying to understand Foldable without first understanding Monoids. I would highly recommend reading further around these topics, including the excellent Typeclassopedia as a starting point (in this context, mostly the sections on Monoid and Foldable).

Upvotes: 2

Enlico
Enlico

Reputation: 28500

In

data LinkedList a = Empty | Cons a (LinkedList a)

you have

  • LinkedList, which is a type constructor: it takes as argument the general type a and gives you back the type LinkedList a;
  • Cons, which is a value constructor: it takes as argument a value of general type a and a value of type LinkedList a.

On the other hand, here

  foldMap f (a `Cons` ll) =  LinkedList (f a)  (foldMap f ll)

you're using LinkedList as if was a value constructor, which is erroneous.

Upvotes: 4

Related Questions