My Answer to 20 Intermediate Haskell Exercises

• Fluffy

class Fluffy f where
  furry :: (a -> b) -> f a -> f b

-- Exercise 1
-- Relative Difficulty: 1
instance Fluffy [] where
  furry f (x:xs) = (f x):(furry xs)
  furry _ []     = []

-- Exercise 2
-- Relative Difficulty: 1
instance Fluffy Maybe where
  furry Nothing = Nothing
  furry Just a  = Just $ f a
-- works like fmap

-- Exercise 3
-- Relative Difficulty: 5
instance Fluffy ((->) t) where
  furry g f x = g $ f x
-- works like (.)

newtype EitherLeft  b a = EitherLeft  (Either a b)
newtype EitherRight a b = EitherRight (Either a b)

-- Exercise 4
-- Relative Difficulty: 5
instance Fluffy (EitherLeft t) where
  furry f (EitherLeft (Left  a)) = EitherLeft (Left $ f a)
  furry _ (EitherLeft (Right b)) = EitherLeft (Right b)

-- Exercise 5
-- Relative Difficulty: 5
instance Fluffy (EitherRight t) where
  furry f (EitherRight (Right a)) = EitherRight (Right $ f a)
  furry _ (EitherRight (Left  b)) = EitherRight (Left  b)

The typeclass Fluffy is just like Functor, with furry works like fmap.

• Misty

class Misty m where
  banana :: (a -> m b) -> m a -> m b
  unicorn :: a -> m a
  -- Exercise 6
  -- Relative Difficulty: 3
  -- (use banana and/or unicorn)
  furry' :: (a -> b) -> m a -> m b
  furry' f = banana $ unicorn `furry` f

-- Exercise 7
-- Relative Difficulty: 2
instance Misty [] where
  banana  f (x:xs) = (f x) ++ (banana f xs)
  banana  _ []     = []
  unicorn a = [a]

-- Exercise 8
-- Relative Difficulty: 2
instance Misty Maybe where
  banana f Nothing  = Nothing
  banana f (Just a) = f a
  unicorn = Just

-- Exercise 9
-- Relative Difficulty: 6
instance Misty ((->) t) where
-- type signature for banana
  banana f g t = f (g t) t
  unicorn a _  = a
-- here's the type signature for banana and unicorn
-- banana  :: (a -> t -> b) -> (t -> a) -> t -> b
-- unicorn :: a -> t -> a
-- so it is almost certain that this is the only possiable implemention

-- Exercise 10
-- Relative Difficulty: 6
instance Misty (EitherLeft t) where
  banana f (EitherLeft (Left  a)) = f a
  banana _ (EitherLeft (Right b)) = EitherLeft (Right b)
  unicorn  = EitherLeft `furry` Left

-- Exercise 11
-- Relative Difficulty: 6
instance Misty (EitherRight t) where
  banana f (EitherRight (Right a)) = f a
  banana _ (EitherRight (Left  b)) = EitherRight (Left b)
  unicorn  = EitherRight `furry` Right

-- Exercise 12
-- Relative Difficulty: 3
jellybean :: (Misty m) => m (m a) -> m a
jellybean = banana id

-- Exercise 13
-- Relative Difficulty: 6
apple :: (Misty m) => m a -> m (a -> b) -> m b
apple = furry' $ flip ($) 
-- if m is List Monad, apple [1, 2, 3] [(+1), (*2), (/3)] means something 
-- like zipWith ($) [1, 2, 3] [(+1), (*2), (/3)]

-- Exercise 14
-- Relative Difficulty: 6
moppy :: (Misty m) => [a] -> (a -> m b) -> m [b]
mpppy [] _     = unicorn []
moppy (a:as) f = banana (\x -> banana (\xs -> unicorn (x:xs)) (moppy as f)) (f a)  
-- the \x thing banana is liftM2 (:) in disguis
-- this implentation is indeed a moppy one.

-- Exercise 15
-- Relative Difficulty: 6
-- (bonus: use moppy)
sausage :: (Misty m) => [m a] -> m [a]
sausage mas = moppy mas id

-- Exercise 16 
-- Relative Difficulty: 6
-- (bonus: use apple + furry')
banana2 :: (Misty m) => (a -> b -> c) -> m a -> m b -> m c
banana2 fabc ma mb = apple mb $ furry' f ma

-- Exercise 17
-- Relative Difficulty: 6
-- (bonus: use apple + banana2)
banana3 :: (Misty m) => (a -> b -> c -> d) -> m a -> m b -> m c -> m d
banana3 fabcd ma mb mc
    = apple mc (banana2 fabcd ma mb)

-- Exercise 18
-- Relative Difficulty: 6
-- (bonus: use apple + banana3)
banana4 :: (Misty m) => (a -> b -> c -> d -> e) -> m a -> m b -> m c -> m d -> m e
banana4 fabcde ma mb mc md
    = apple md (banana3 ma mb mc)

Typeclass Misty is dreadful Modad typeclass, with banana is =<<, unicorn is return and furry' is liftM. Other function like jellybean is >>= and apple is forM.

newtype State s a = State {
  state :: (s -> (s, a))
}

-- Exercise 19
-- Relative Difficulty: 9
instance Fluffy (State s) where
  furry f st = State ((\f (a, b) -> (a, f b)) (state st))

-- Exercise 20
-- Relative Difficulty: 10
instance Misty (State s) where
  banana  f sa st = f $ (\(a, b) -> b) $ state sa st
  unicorn a st    = (st, a)

There is a simlar example in the book Real World Haskell, chapter named Chapter 10. Code case study: parsing a binary data format, which build the essence of a State monad from scretch without even introducing the concept of Monad. Very inspering.