Defining monad from scratch in Haskell

Question

After studying about monads in Haskell — a subject that is very compelling for everything that implies — I wonder if I could define a monad on my own without using the already defined typeclasses.

Instead of making Monad an instance of Functor, I just want to define a monad per se, with it's own fmap function (Also I wanted to change some function names such as return and call it unit).

A monad may be defined by the bind operator (>>=) and the function return, but it also may be defined in terms of return and join since this last function it can be expressed in terms of the bind operator: join m = m >>= id. So a monad could be (technically) defined in terms of return and join and nothing else. The function fmap is required (and the base of existence of a Functor in Haskell), but also could be defined in terms of return, for it may be defined also (I think) as follows: fmap f m = m >>= return . f (before edit it was written, fmap f m = return . f; it was obviously a typo).

Yet I know this wouldn't be as efficient as using the predefined Monad typeclass, it's just to understand better the Haskell language.

How can I accomplish that? This is a depiction of this concept out of my head, right now, so it's not useful code:

-- Just a sketch
infixr 9 ∘
(∘) :: (b -> c) -> (a -> b) -> a -> c
(∘) g f x = g (f x)
--(f ∘ g) x = f (g x)

-- My own 'fmap'
--mapper id  =  id
--mapper (f ∘ g) = mapper f ∘ mapper g


-- My monad
class MyMonadBase (m :: * -> *) where
    unit :: a -> m a   --return

    join :: m (m a) -> m a
    join = (>>= id)

    mapper f m = m >>= unit ∘ f


--Testing:
data Tree a = Leaf a | Branch (Tree a) (Tree a)

instance MyMonadBase Tree where
    unit = Leaf
    join (Leaf x) = x
    join (Branch l r)  = Branch (join l) (join r)

Am I in the right track (conceptually)?

`fmap f = return . f` – this doesn't work. The type of `return . f` is `a -> m b`, not `m a -> m b`. Neither does `mapper` work: you can't pattern-match on `id` or `∘` unless you define them as _data constructors_. — Anyway... I don't quite see what you're trying to achieve here. A monad is, fundamentally, first of all a functor. Even if it's technically possible to omit that requirement, doesn't mean it makes sense to do that. Haskell98 did, and it was quickly realised that this wasn't a good idea. — leftaroundabout, Dec 30 '15 at 19:11
`(g <$>) = (return . g =<<)`, i.e. `return` is not enough, you also need bind for this. `(k =<<) = join . (k <$>)`, so you must have `(<$>)` (i.e. `fmap`) with the `join`. cf. http://stackoverflow.com/questions/34545818/is-monad-bind-operator-closer-to-function-composition-chaining-or-functi/34561605#34561605 — Will Ness, Jan 03 '16 at 11:26

score 3 · Answer 1 · answered Dec 30 '15 at 19:11

Some small corrections:

A monad may be defined by the bind operator (>>=) and the function return, but it also may be defined in terms of return and join since this last function it can be expressed in terms of the bind operator: join m = m >>= id.

The conclusion ("[a monad] also may be defined in terms of return and join") is correct, but the premise ("since [join] can be expressed in terms of the bind operator") does not imply it. Instead you must show that the operator you are omitting -- the bind operator -- may be defined in terms of the things you have -- return and join. Once you try to do this, you see why it is so critical that a monad also be a functor:

m >>= f = join (fmap f m)

The function fmap is required (and the base of existence of a Functor in Haskell), but also could be defined in terms of return, for it may be defined also (I think) as follows: fmap f m = return . f

That's not quite a correct definition of fmap -- and you should be suspicious indeed, since the right hand side doesn't mention m! A correct version would be:

fmap f m = m >>= return . f

But now this is a circular definition, since above we planned on defining (>>=) in terms of fmap. So if you want to make return and join the basic operations of Monad, you really do need to implement fmap separately.

I know this wouldn't be as efficient as using the predefined Monad typeclass

I don't see any reason to believe this a priori. The reason (>>=) is chosen over join is not because it is more efficient, but because it is such a natural operation when using monads in programming.

As for your actual code, I think it looks fine with two caveats:

I strongly suspect your definition of mapper does not do what you think it does. In the line mapper id = id, the pattern id on the left hand side matches all incoming values, and the variable id on the right hand side returns them unchanged. The line mapper (f ∘ g) = mapper f ∘ mapper g is simply not valid Haskell. (Perhaps these two lines were intended to be documentation of the laws required of mapper rather than actual code?)
It is strange to offer default implementations of join and mapper in terms of (>>=) -- both for the reasons above (all three are fundamental and must be defined) and because (>>=) is not a class operation, hence can't be defined by the user in a meaningful way.

`join . fmap f` *will* be slower than `(f =<<)` for many functors. — dfeuer, Dec 30 '15 at 21:46

score 2 · Accepted Answer · answered Dec 31 '15 at 08:31

Okay, it wasn't that difficult. I had the misconception that implementing a own monad type will be extremely complex, but it's just applying the definition.

-- My monad
class MyMonad m where
    unit :: a -> m a
    join :: m (m a) -> m a
    mapf :: (a -> b) -> m a -> m b


--Testing MyMonad
data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show)

instance MyMonad Tree where
    unit = Leaf
    join (Leaf x) = x
    join (Branch l r) = Branch (join l) (join r)
    mapf f (Leaf x) = Leaf (f x)
    mapf f (Branch l r) = Branch (mapf f l) (mapf f r)

t = Branch (Branch (Leaf 1) (Leaf 3)) (Branch (Leaf 2) (Leaf 4))


-- My bind (just for completeness, not that I need it for this example)
(>>>) :: MyMonad m => m a -> (a -> m b) -> m b
xs >>> f = join (mapf f xs)


-- Testing my bind
extr :: Integer -> Tree Integer
extr x = Branch (Leaf (x^2)) (Leaf (2^x))

t >>> extr
--Branch (Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 9) (Leaf 8))) 
--       (Branch (Branch (Leaf 4) (Leaf 4)) (Branch (Leaf 16) (Leaf 16)))

Defining monad from scratch in Haskell

2 Answers2