CODEWITHSUNDEEP
haskellfunctor
Harry Aris
Harry Aris

Reputation: 11

Change parameterised type List to instance of the Functor class

I'm new with the Functor, so I have parameterised type List like this:

data List a = Empty | One a | Append (List a) (List a)

and the question asked me to change it into an instance of the Functor class in Haskell syntax. I'm struggling in define for each fmap

Upvotes: 0

Views: 106

Answers (1)

Random Dev
Random Dev

Reputation: 52290

Here is your structure again (a bit nicer formated):

data List a 
  = Empty 
  | One a 
  | Append (List a) (List a)

You are asked to define a Functor-Instance for that so let's start by pattern-matching on the 3 constructors:

instance Functor List where
  fmap f Empty = ...
  fmap f (One a) = ...
  fmap f (Append a b) = ...

in the Empty there is (aside from bottom-values like undefined, ...) really only one possibility - you have to return a List a - Empty is possible, for One you'd need one a-value (which you don't have) and for Append you'd need two Lists again. Sure you could take Append Empty Empty but remember one of the functor-laws states fmap id l === l for all Lists l (meaning exactly the same - not Haskells Eq!) - so there is only one choice:

instance Functor List where
  fmap _ Empty = Empty

for One it's similar: you need fmap id (One a) === One a so the constructor is fixed and for the general case fmap :: (a -> b) -> List a -> List b you see that you have to use f on the wrapped a-value in One:

instance Functor List where
  fmap f (One a) = One (f a)

Finally for the Append-case. By now you should know that this needs to result in Append (..) (..) again (functor-law) and the two arguments to Append on the right-side needs to be List b. Now how to get List b when you have List a? If you look around: fmap f :: List a -> List b so you have a way to turn List as (of which you have two in scope) into List bs (maybe not surprising as Append is recursive too) and again the functor-laws only let you one choice (why?):

instance Functor List where
  fmap f (Append a a') = Append (fmap f a) (fmap f a')

so you get:

instance Functor List where
  fmap _ Empty = Empty
  fmap f (One a) = One (f a)
  fmap f (Append a b) = Append (fmap f a) (fmap f b)

PS: Normally - not Homework - you could do:

{-# LANGUAGE DeriveFunctor #-}
module ... where

data List a 
  = Empty 
  | One a 
  | Append (List a) (List a)
  deriving Functor

and the GHC will figure this out for you ;)

Upvotes: 1

Related Questions