Why Am I Getting GHC Couldn't Match Type Error in Functor Instance?

user_9985445 0
Viewed 67

I am trying to write a Functor instance:

module TreeN where

data TreeN a = LeafN a | ParentN a [TreeN a] deriving (Eq, Show)

instance Functor TreeN where

fmap f (LeafN x) = LeafN (f x)
fmap f (ParentN x children) = (ParentN (f x) (TreeN.fmap f children))

And I get this Error:

src/TreeN.hs:7:1: error:
    • Couldn't match type ‘TreeN t’ with ‘[TreeN t]’
      Expected type: (t -> a) -> [TreeN t] -> [TreeN a]
        Actual type: (t -> a) -> TreeN t -> TreeN a
    • Relevant bindings include
        fmap :: (t -> a) -> [TreeN t] -> [TreeN a]
          (bound at src/TreeN.hs:7:1)
  |
7 | fmap f (LeafN x) = LeafN (f x)
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...
Failed, no modules loaded.

It is a mystery to me why GHC thinks I want to wrap fmap's input and output in another layer of structure.

I also tried spelling out this:

map :: (a -> b) -> f a -> f b

but that results in different errors. I cannot tell whether GHC is erroring out because it saw the same thing twice, or whether you are supposed to be explicit about this and being explicit about it exposes some other problem.

What am I doing wrong?

functor ghc haskell
1 Answers

Your parentN has a list of TreeNs, so you need to perform a mapping over all children:

instance Functor TreeN where
    fmap f (LeafN x) = LeafN (f x)
    fmap f (ParentN x children) = ParentN (f x) (map (fmap f) children)

Your implementation of the Functor is however the "standard" implementation, you can make use of the DeriveFunctor language extension and work with:

{-# LANGUAGE DeriveFunctor #-}

data TreeN a = LeafN a | ParentN a [TreeN a] deriving (Eq, Functor, Show)
user_675790
Related