We are given

type ID = Int
data LST a
  = Leaf ID a
  | Node ID [LST a]
    deriving (Show, Eq)

How may I write a functor instance for LST, such that

instance Functor LST where
  fmap = something

CodePudding user response：

You can let Haskell do the work with the DeriveFunctor extension ^[ghc-doc]:

{-# LANGUAGE DeriveFunctor #-}

type ID = Int
data LST a
  = Leaf ID a
  | Node ID [LST a]
  deriving (Show, Eq, Functor)

CodePudding user response：

There are, in general, two ways to construct an Lst a value, so start by enumerating them and noting the types of values bound to each name:

fmap f (Leaf i x) = ...  -- f :: a -> b, i :: Int, x :: a
fmap f (Node i xs) = ... --  f :: a -> b, i :: Int, xs :: [a]

Assuming that the results must depend on f somehow, there are only a couple of options for doing so:

1. Apply f to x to get a value of type b
2. Map f over xs to get a value of type [b].

Using this, you can probably make a good guess at what the right-hand side of each definition should be. Once you've done that, you can check your definitions against the functor laws, specifically,

fmap id (Leaf i x) == id (Leaf i x)
fmap id (Node i xs) == id (Node i xs)

fmap (f.g) (Leaf i x) == fmap f (fmap g (Leaf i x))
fmap (f.g) (Node i xs) == fmap f (fmap g (Node i xs))