Understanding Monads boxing

Today on #haskell@freenode I had an interesting discussion. It all started when I asked if the following statements make any sense: 

Just 5 >>= \x -> Just $ x+1
what this does is basically unwraps Just, adds 1 to its value and returns Just. (*
return (Just 5) >>= \y -> y >>= \x -> Just $ x+1
what this does is basically unwraps the monadic value of Just 5, so we have Just 5.
So we have return (Just 5) >>= \y -> y == Just 5. Now (*) applies here.

Let’s check the types:

Prelude> :t Just 5
Just 5 :: Num a => Maybe a
Prelude> :t return (Just 5)
return (Just 5) :: (Monad m, Num a) => m (Maybe a)

So, basically, my question was (as can be seen from the statement above), how is it possible to convert m (Maybe a) to Maybe a? And, if m (m a) -> m a is possible, why isn’t m a -> a possible?

Well, m a -> a can be possible for some monads, for example for the Maybe monad, if we define it like:

fromJust (Just x) = x

But it’s not something that can be easily implemented for just any monad.

Now, as for why m (m a) -> m a is possible (and, in general m (m (… (m a) …)) -> m a), we can take a look at the definition of join, which is:

join x = x >>= id

So, if we try to do something like this: 

Prelude> join $ Just (Just 5)
Just 5
Prelude> :t Just (Just 5)
Just (Just 5) :: Num a => Maybe (Maybe a)
Prelude> :t Just 5
Just 5 :: Num a => Maybe a
Prelude> join $ Just (Just 5)
Just 5
Prelude> :t join $ Just (Just 5)
join $ Just (Just 5) :: Num b => Maybe b

We can see basically how it “unboxes” stuff, and in my statement above I implicitly used join, which is the underlined part.

But how does it really work?

Well, if we look at the type of the bind operator:

Prelude> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

We can now start experimenting. What if we set a = m c?

We get m (m c) -> (m c -> m b) -> m b. Can we find such a function that satisfies this?

For (a -> m b) we can basically use the following lambda \x -> return x
So, for (m a -> m b), what if we omit return, and instead try \x -> x? 

Prelude> Just (Just 5)
Just (Just 5)
Prelude> Just (Just 5) >>= \x -> x
Just 5
Prelude> :t Just (Just 5) >>= \x -> x
Just (Just 5) >>= \x -> x :: Num b => Maybe b
Prelude> :t Just (Just 5)
Just (Just 5) :: Num a => Maybe (Maybe a)
Prelude> :t (Just 5)
(Just 5) :: Num a => Maybe a

So, by using return, in the example of m a -> (a -> m b) -> m b we give back a “boxed” value, because we have \x -> return x where x = a, and return x = m a.

But, by not using return in the example of m (m a) -> (m a -> m b) -> m b we give back the same value that we receive, because we have \x -> x where x = m a, and the lambda expression will evaluate to m a.

So, with this we have shown how it’s possible to convert m (m a) to m b, and thus in general m (m (… (m a) …)) to m b.

Some interesting excerpts from the chat (please note that some parts are removed):

 the difference between "return $ Just 5" and "Just 5" is that the first is a monadic value
  (instance of Monad), and the second is only instance of data Maybe?
 BoR0: Maybe is an instance of Monad, the difference is this:
 > return $ Just 5 :: [Maybe Int]
  [Just 5]
 > return $ Just 5 :: Maybe (Maybe Int)
  Just (Just 5)
 BoR0: Maybe is an instance of Monad, "Monad m => m" says "any monad will work"
 BoR0: So "(>>=) :: Monad m => m a -> (a -> m b) -> m b" says it'll work for *any* Monad,
  even if if you don't know yet which one
 BoR0: There's no reason why a monad cannot contain another monad inside
 > return 5 :: [Int]
  [5]
 aha, okay. so return $ Just 5 is doubly "wrapped"
 BoR0: Yes
 BoR0: ^
 so if we have return x = Just x for Maybe monad, why doesn't return $ Just 5 give Just (Just 5)
  to us?
 BoR0: It will, if you ask for it
 > return (Just 5) :: Maybe (Maybe Int)
  Just (Just 5)
 but what does it do without specifying :: ... ?
 BoR0: Without the type signature it's polymorphic, it can be any Monad instance
 polymorphic! that clarifies it! great
 BoR0: Yes, all typeclasses are polymorphic, unless you specify a type OR type inference sees
  which type you wanted (actually, this is the only way, the type annotation just explicitly tell the
  type inference what you want :)
 I somewhere read that IO String can't be converted to String. but with this discussion I think
  the opposite, what is wrong now?
 so what held for Maybe monad (extracting x from Just x) doesn't necesarilly hold for IO monad?
 BoR0: For Maybe, you weren't really extracting. You were putting the value back into a Just
  at the end with return. All monadic expressions have a return at the end.
 BoR0: Yes, some *specific* monads may provide tools for extracting values (i.e. Maybe
  and list, for example). But the generic monad class does not provide a way to do that
 BoR0: Since IO doesn't provide a function to extract values, there's no way to get them out
 BoR0: monads allow you to go from an arbitrary number of applications of M to A to just M A

Functors

In Haskell, the Functor instance is only supposed to handle the mapping between objects, under the following rules:

1. Identity (fmap id = id)
2. Composition fmap f . fmap f = fmap (f o g)

So, if we want to declare a Functor instance over some type, that’s all we need to care about.
Functors are nothing more than that (to handle fmap for some actual type). The type definition of fmap is:

fmap :: Functor f => (a -> b) -> f a -> f b

So, from this we can see that the first parameter is a morphism, and the second parameter is the actual object. So, for instance, we can have:

fmap floor [1.5, 2.5, 3.5]

And we can see how our list “morphs” from a list with doubles to a list with integers!

Prelude> :t [1.5, 2.5, 3.5]
[1.5, 2.5, 3.5] :: Fractional t => [t]
Prelude> :t [1, 2, 3]
[1, 2, 3] :: Num t => [t]
Prelude> :t fmap floor [1.5, 2.5, 3.5]
fmap floor [1.5, 2.5, 3.5] :: Integral b => [b]

Another interesting thing to have a look at is the instance for ((->) r), which is defined as:

instance Functor ((->) r) where
    fmap f g = (\x -> f (g x))

Now, by having this definition, and that of fmap’s, we can apply ((->) r) to fmap to get:


fmap :: Functor f -> (a -> b) (r -> a) (r -> b)
    fmap f g = (\x -> f (g x))

So, with this we can see that we can apply fmap to functions too!


Prelude> fmap (* 123) succ 3
492
Prelude> fmap (* 100) (\x -> x + 1) 123
12400

And, for some more theory (if you care), Wikipedia states that Functors are morphisms, and for morphisms:

In many fields of mathematics, morphism refers to a structure-preserving mapping from one mathematical structure to another. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms are functions; in linear algebra, linear transformations; in group theory, group homomorphisms; in topology, continuous functions, and so on.
In category theory, morphism is a broadly similar idea, but somewhat more abstract: the mathematical objects involved need not be sets, and the relationship between them may be something more general than a map.

Music fun

Here is a tiny example that I’ve been playing around with the other day:

data Note = C | D | E | F | G | A | B deriving (Show, Enum, Bounded, Eq, Read)

buildTuple :: [a] -> [(Maybe a, Maybe a)]
buildTuple xs = zip z $ Nothing:z
  where
  z = map Just xs

getPreviousElement :: [Note] -> Maybe Note
getPreviousElement [] = Nothing
getPreviousElement xs = snd $ last $ buildTuple xs

addNote :: [Note] -> [Maybe Note]
addNote xs = map Just xs ++ [getPreviousElement xs >>= succNote]

succNote :: Note -> Maybe Note
succNote n
    | n == maxBound = Just minBound
    | otherwise     = Just $ succ n

parseBrackets :: String -> String
parseBrackets ('{':xs) = '[' : parseBrackets xs
parseBrackets ('}':xs) = ']' : parseBrackets xs
parseBrackets (x:xs)   = x : parseBrackets xs
parseBrackets x        = x

main :: IO [Maybe Note]
main = getLine >>= \xs -> return (addNote (read (parseBrackets xs) :: [Note]))

This example demonstrates a couple of things:

1. How we can use the Haskell’s type system to define a list of Notes
2. The use of the zip function, to show how easy it is to get a previous element in a list (what buildTuple does is e.g. for [A,B,C] it would produce [(Just A, Nothing), (Just B, Just A), (Just C, Just B)], so that we have a track of previous elements)
3. It demonstrates reading and playing around with IO and parsing stuff on our own way

The ((->) a) Monad instance (aka Function monad)

Today on #haskell@freenode I had this interesting discussion. I started with the question:

could anyone explain to me how is replicate >>= id equal to \x -> replicate x x?

And ended up with the answer:

f >>= id = (\x -> f x x) whenever f is a function

But let’s dig through the whole process and see how this magic is done.

First, let’s check the type of the bind operator (>>=):

Prelude> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

And let’s check how bind is defined for ((->) r) Monad: 

instance Monad ((->) r) where  
    return x = \_ -> x  
    h >>= f = \w -> f (h w) w

Next, let’s check the type of (replicate >>=):

Prelude> :t (replicate >>=)
(replicate >>=) :: ((a -> [a]) -> Int -> b) -> Int -> b

Patterns emerge. If we set m = ((->) r), we get:

Monad m => m a -> (a -> m b) -> m b
Monad m => ((->) r) a -> (a -> ((->) r) b) -> ((->) r) b
Monad m => (r -> a) -> (a -> (r -> b)) -> r -> b
Monad m => (r -> a) -> (a -> r -> b) -> r -> b

So, if we try to construct a function from this type, we understand from the type that it’s a function that takes 3 parameters, where the first two parameters are functions.

But before we go into that, how did we know that we should set m = ((->) r) in the first place?

From replicate’s type, we get: 

Prelude> :t replicate
replicate :: Int -> a -> [a]

So, we have: Int -> (a -> [a]) = (->) Int (a -> [a]) = ((->) Int) (a -> [a])
And the generalization of that: ((->) r) (a -> [a])

So, back to our construction for f: we know that it should look something like: f x y z = ?
But from its type, we can see that the first parameter accepts an ‘r’ as input, and the second parameter accepts an input of the form (a -> r).

So we have something like: f x y z = y (x z) z (which is equivalent to the bind operator that we’ve shown before for the ((->) r) Monad instance)

So, if we apply replicate and id to f, we get: f replicate id z = id (replicate z) z f z = id (replicate z) z which equals to replicate z z

Now we can play with our function! 

Prelude> f 3
[3,3,3]
Prelude> f 4
[4,4,4,4]
Prelude> f 5
[5,5,5,5,5]
Prelude> map (\x -> replicate x x) [1..10]
[[1],[2,2],[3,3,3],[4,4,4,4],[5,5,5,5,5],[6,6,6,6,6,6],[7,7,7,7,7,7,7],[8,8,8,8,
8,8,8,8],[9,9,9,9,9,9,9,9,9],[10,10,10,10,10,10,10,10,10,10]]
Prelude> concat $ map (\x -> replicate x x) [1..10]
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9
,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10]
Prelude> concat $ map (replicate >>= id) [1..10]
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9
,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10]
Prelude> concatMap (replicate >>= id) [1..10]
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9
,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10]
Prelude> concatMap f [1..10]
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9
,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10]
Prelude>

E.g.: Try to understand how it will work for “length”, for instance.

We have that: 

Prelude> :t length
length :: [a] -> Int
Prelude> :t (length >>=)
(length >>=) :: (Int -> [a] -> b) -> [a] -> b

So, by looking at the definition for ((->) r) Monad, can you see what it does? Here are some hints:

Prelude> let f x y = (x, y)
Prelude> (length >>= f) [1,2,3]
(3,[1,2,3])

Helpful excerpt from LYAH:

The implementation for >>= seems a bit cryptic, but it’s really not all that. When we use >>= to feed a monadic value to a function, the result is always a monadic value. So in this case, when we feed a function to another function, the result is a function as well. That’s why the result starts off as a lambda. All of the implementations of >>= so far always somehow isolated the result from the monadic value and then applied the function f to that result. The same thing happens here. To get the result from a function, we have to apply it to something, which is why we do (h w) here to get the result from the function and then we apply f to that. f returns a monadic value, which is a function in our case, so we apply it to w as well.

The full log: 

 could anyone explain to me how is replicate >>= id equal to \x -> replicate x x
 @type (>>=)
 Monad m => m a -> (a -> m b) -> m b
 bor0: With m = ((->) r), what is the specialized type of (>>=)?
 r -> a -> (a -> (r -> a) b) -> r -> b ?
 errr
 It’s (->) r a -> (a -> (->) r b) -> (->) r b
 I can't understand prefix arrow
 what does that mean?
 Which is (r -> a) -> (a -> r -> b) -> r -> b
 parentheses are important
 (+) 4 5 = 4 + 5
 (->) r a  is (r -> a)
 (r -> a) -> (a -> r -> b) -> r -> b
 bor0: Can you come up with a definition for the function
  f :: (r -> a) -> (a -> r -> b) -> r -> b?
 (keep in mind that a -> b -> c is really a -> (b -> c) )
 I can see that it takes three parameters, the first two being another function
 bor0: Correct
 hint: there is only one way to write it
 isn't that just (.)?
 no
 identity: no
 or foo f f1 = f1 . f?
 f x y z = z x y ?
 bor0: It must return a “b”. Which parameter can you use to get a b?
 the y in "f x y z"
 bor0: Correct. f ra arb r = arb something something
 oh right, so f x y z = y x z?
 stop guessing
 :p
 bor0: You’ll need to apply it to something of type a and something of type r. Can you figure out
  how?
 ion: is this correct? f x y z = y (x z) z 
 :t let f x y z = y (x z) z in f
 (t2 -> t1) -> (t1 -> t2 -> t) -> t2 -> t
 Kinda messy with the t's, but that's the same as: (r -> a) -> (a -> r -> b) -> r -> b
 bor0: Yes. Congrats. Now, what is f replicate id?
 So you got it
 f z = id (replicate z) z
 I got it from here
 thank you. but, can you please explain to me the (-> r) part? what did you do there?
 Your original expression replicate >>= id uses the Monad instance for ((->) r). Have you
  learned about Monads?
 I only know about monads in general. how can I see that replicate >>= id uses ((->) r) monad
  instance?
 :t replicate
 Int -> a -> [a]
 :t (>>=)
 Monad m => m a -> (a -> m b) -> m b
 replicate :: (->) Int (a -> [a])
 BoR0: In order for  Int -> t -> [t] to unify with m a
 @type (replicate >>=)
 ((a -> [a]) -> Int -> b) -> Int -> b
 sorry, I still can't see how you extracted ((->) r) from that
 Int -> (t -> [t]) = (->) Int (t -> [t]) = ((->) Int) (t -> [t])
 ahhh right
 @src sequence
 sequence []     = return []
 sequence (x:xs) = do v <- x; vs <- sequence xs; return (v:vs)
 @src liftM2
 liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }
 bor0: This may or may not be helpful: http://heh.fi/haskell/functors/#function-instance
 which matches against m a with m = ((->) Int) and a = (t -> [t])
 > (do f <- replicate; n <- id; return (f n)) 5
   [5,5,5,5,5]
 BoR0: The function monad instance is one where "running" a function means applying it to the
  parameter to which the whole function has been applied
 BoR0: Check this out:
 > (do f <- replicate; id f) 5
   [5,5,5,5,5]
 > (do x <- id; y <- reverse; z <- map toUpper; return (x,y,z)) "hello"
   ("hello","olleh","HELLO")
 > join replicate 5
   [5,5,5,5,5]
 > sequence [id, (+2), (*2), (^2), (2^)] 5
   [5,7,10,25,32]
...
 f >>= id = (\x -> f x x) whenever f is a function

Last element of list with proof

We have last’ defined like: 

last' [x] = x
last' (x:xs) = last' xs (*)

Base case: A list of one element is equal to that element itself.

Inductive step: Assume that last’ (x:xs) returns the last element of the list.
Then, if last’ (x:xs) holds, last’ (y:x:xs) must also hold.

We must show that it holds for y:x:xs.

Set zs = x:xs and obtain:
last’ (y:zs) = (*) = last’ zs = last’ (x:xs) = inductive assumption = last element of the list

So the recursion chops elements from beginning until it reaches one element, which will be the last element from our list.