Naive psuedocode implementations of common Haskell monads

PreludeMonads.hs

type [a] = [] | a : [a]
instance Monad (a ↦ [a]) where

  fmap ∷ (a → b) → List a → List b
  fmap _ [] = []
  fmap f (x : xs) = (f x) : (fmap f xs)

  pure ∷ a → List a
  pure x = x : []

  (<*>) ∷ List (a → b) → List a → List b
  [] <*> _ = []
  (f : fs) <*> xs = (fmap f xs) ++ (fs <*> xs)

  (>>=) ∷ List a → (a → List b) → List b
  [] >>= _ = []
  (x : xs) >>= k = (k x) ++ (xs >>= k)


type Maybe a = Nothing | Just a
instance Monad (a ↦ Maybe a) where

  fmap ∷ (a → b) → Maybe a → Maybe b
  fmap _ Nothing = Nothing
  fmap f (Just x) = Just (f x)

  pure ∷ a → Maybe a
  pure x = Just x

  (<*>) ∷ Maybe (a → b) → Maybe a → Maybe b
  Nothing <*> _ = Nothing
  (Just f) <*> m = fmap f m

  (>>=) ∷ Maybe a → (a → Maybe b) → Maybe b
  Nothing >>= _ = Nothing
  (Just x) >>= k = k x


type Either e a = Left e | Right a
instance Monad (a ↦ Either e a) where

  fmap ∷ (a → b) → Either e a → Either e b
  fmap _ (Left e) = Left e
  fmap f (Right x) = Right (f x)

  pure ∷ a → Either a
  pure x = Right x

  (<*>) ∷ Either e (a → b) → Either a → Either b
  (Left e) <*> _ = Left e
  (Right f) <*> m = fmap f m

  (>>=) ∷ Either e a → (a → Either e b) → Either e b
  (Left e) >>= _ = Left e
  (Right x) >>= k = k x


type Writer w a = (a, w)
instance Monad (a ↦ (a, w)) where

  fmap ∷ (a → b) → (a, w) → (b, w)
  fmap f (x, w1) = (f x, w1)

  pure ∷ a → (w, a)
  pure x = (x, mempty)

  (<*>) ∷ (w, a → b) → (w, a) → (w, b)
  (f, w1) <*> (x, w2) = (f x, w2 `mappend` w1)

  (>>=) ∷ (a, w) → (a → (b, w)) → (b, w)
  (x, w1) >>= k = (y, w2 `mappend` w1)
    where
      (y, w2) = k x


type Reader r a = r → a
instance Monad (a ↦ r → a) where

  fmap ∷ (a → b) → (r → a) → r → b
  fmap f g r1 = (f ◦ g) r1

  pure ∷ a → r → a
  pure x _ = x

  (<*>) ∷ (r → a → b) → (r → a) → r → b
  (<*>) f g r1 = f r1 (g r1)

  (>>=) ∷ (r → a) → (a → r → b) → r → b
  (>>=) g k r1 = k (g r1) r1


type State s a = s → (a, s)
instance Monad (a ↦ s → (a, s)) where

  fmap ∷ (a → b) → (s → (a, s)) → s → (b, s)
  fmap f sa s1 = (f x, s2)
    where
      (x, s2) = sa s1

  pure ∷ a → s → (a, s)
  pure x s1 = (x, s1)

  (<*>) ∷ (s → (a → b, s)) → (s → (a, s)) → s → (b, s)
  (<*>) sf sa s1 = (f x, s3)
    where
      (f, s2) = sf s1
      (x, s3) = sa s2

  (>>=) ∷ (s → (a, s)) → (a → s → (b, s)) → s → (b, s)
  (>>=) sa k s1 = k x s2
    where
      (x, s2) = sa s1


type Cont c a = (a → c) → c
instance Monad (a ↦ (a → c) → c) where

  fmap ∷ (a → b) → ((a → c) → c) → (b → c) → c
  fmap f ma g =  ma (g ◦ f)

  pure ∷ a → (a → c) → c
  pure a g = g a

  (<*>) ∷ (((a → b) → c) → c) → ((a → c) → c) → (b → c) → c
  (<*>) mf ma g = mf (f ↦ ma (g ◦ f))

  (>>=) ∷ ((a → c) → c) → (a → ((b → c) → c)) → (b → c) → c
  (>>=) ma k g = ma (x ↦ k x g)

The continuation monad was the hardest to figure out, but after you see it it's so clear.