Functor error when using a data inside a data: “cannot construct the infinite type”

Question

While learning more about Haskell's type system, I encountered this toy problem. When I compile the following code:

data SingleData a = SingleData a Int String -- etc.
data DataFail a = DataFail [SingleData a]
instance Functor DataFail where
    fmap f (DataFail xs) = DataFail (map f xs)

I get the dreaded "Occurs check: cannot construct the infinite type: b = SingleData b" message on the definition of fmap. Strangely, the same definition of fmap will work if it is outside of the instance declaration:

fmapWorks f (DataFail xs) = DataFail (map f xs)

Even stranger, implementing Monoid compiles and works just fine:

instance Monoid (DataFail a) where
    mempty = DataFail []
    mappend (DataFail xs) (DataFail ys) = DataFail (xs ++ ys)

I believe that this is somehow a result of using SingleData inside of DataFail, because this works just fine as well:

data DataSuccess a = DataSuccess [a]
instance Functor DataSuccess where
    fmap f (DataSuccess xs) = DataSuccess (map f xs)

Why is Haskell complaining about DataFail's fmap function, and what can I do to fix it?

If you look at the type of fmapWorks you'll see that it's not the type needed for fmap. — augustss

ivanm ivanm · Accepted Answer · 2011-09-20T06:27:54

The "Occurs check" error isn't that dreaded...

The problem is the function provided to fmap. Try this:

instance Functor SingleData where
  fmap f (SingleData a i s) = SingleData (f a) i s

instance Functor DataFail where
  fmap f (DataFail sds) = DataFail $ map (fmap f) sds

So, the actual error is your usage of map: the type doesn't match. Functor expects it to be of type a -> b, but the way you're using it is of type SingleData a -> SingleData b; the extra Functor instance for SingleData allows you to use fmap to apply the function directly to the value inside of it.

Functor error when using a data inside a data: “cannot construct the infinite type”

1 Answers