Search code examples
haskellfunctor

How is functor chaining done


Hello i am reading Real World Haskell and i have stumbled upon this example from Chapter 10 - Parsing a raw PGM file where it explains how to eliminate boilerplate code using functor chaining:

(>>?) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>? _ = Nothing
Just v  >>? f = f v

-- L.ByteString -> Maybe (Int, L.ByteString)
getNat s = case L8.readInt s of
             Nothing -> Nothing
             Just (num,rest)
                 | num <= 0    -> Nothing
                 | otherwise -> Just (fromIntegral num, rest)

parseP5_take2 :: L.ByteString -> Maybe (Greymap, L.ByteString)
parseP5_take2 s =
    matchHeader (L8.pack "P5") s       >>?
    \s -> skipSpace ((), s)           >>?
    (getNat . snd)                    >>?
    skipSpace                         >>?
    \(width, s) ->   getNat s         >>?
    skipSpace                         >>?
    \(height, s) ->  getNat s         >>?
    \(maxGrey, s) -> getBytes 1 s     >>?
    (getBytes (width * height) . snd) >>?
    \(bitmap, s) -> Just (Greymap width height maxGrey bitmap, s)

skipSpace :: (a, L.ByteString) -> Maybe (a, L.ByteString)
skipSpace (a, s) = Just (a, L8.dropWhile isSpace s)

I do not understand the following: If the >>? operator takes a Maybe a and applies a method but returns a Maybe b then how come the skipSpace and getNat fit in since both accept an unboxed (non-maybe) argument.
So you have a Maybe a and you pass it through a >>? ,it means you will have a Maybe b...when is this Maybe b unboxed to be given to the next method ? ( in our case getNat or skipSpace ?

What i mean is that after each >>? and before each method what you have is a Maybe something ,while the next method is of type nextmethod::something->Maybe somethingElse. When is the Maybe something unboxed into something for the method that uses it ?


method_0 >>? [Maybe something] method_1 >>? [Maybe somethingElse] method_2

So in the [ ] i have written the types that result from >>? just before being given to the methods.
method_1 accepts a something while method_2 accepts a somethingElse. Who does the unboxing for these 2 methods?


Solution

  • Here's a different approach to explain why >>? is useful.

    If these were ordinary functions of type a -> b, we could just chain them together using function composition.

    f :: a -> b
    g :: b -> c
    h :: c -> d
    
    h . g . f :: a -> d
    

    Or introducing a new operator f >>> g = g . f as "reverse composition",

    f >>> g >>> h :: a -> d
    

    However, the Maybe complicates things, because now the return type of one function does not match the input of the next:

    f' :: a -> Maybe b
    g' :: b -> Maybe c
    h' :: c -> Maybe d
    
    f' >>> g' >>> h'  -- type check errors
    

    However, since Maybe is a functor, we can use fmap to apply g' to the return value of f'.

    x :: a
    f' x :: Maybe b
    fmap g' (f' x) :: Maybe (Maybe c)
    fmap h' (fmap g' (f' x)) :: Maybe (Maybe (Maybe d))
    

    But the more we do this, the more the wrappers pile up; eventually, we need to try to get the value of type d out from under all the wrappers.

    Certain functors allow us to write a function I'll call join that "reduces" a layer of wrappers by "joining" them together. Maybe is one of those functors:

    join :: Maybe (Maybe a) -> Maybe a
    join Nothing = Nothing
    join (Just Nothing) = Nothing
    join (Just (Just x)) = Just x
    

    Here, if both wrappers are Just, we eliminate one. If Nothing appears in the pile at all, we return `Nothing. Now, we could write our chained function like

    fmap g' (f' x) :: Maybe (Maybe c)
    join (fmap g' (f' x)) :: Maybe c
    fmap h' (join (fmap g' (f' x))) :: Maybe (Maybe d)
    join (fmap h' (join (fmap g' (f' x)))) :: Maybe d
    

    That's still a bit of boiler plate, but notice that after each call to fmap, we call join on the return value. We can abstract that away using a new operator >>?, which simply maps its right-hand operand over the left-hand operand, then reduces the result.

    >>? :: Maybe a -> (a -> Maybe b) -> Maybe b
    m >>? f = join (fmap f m)
    

    Using the new operator, we can simplify the long chain of calls to fmap and join to

    f' x >>? g' >>? h'
    

    It should be easy enough to convince yourself that Just (f' x) == fmap f' (Just x), so we can further smooth our chain out to look like

    Just x >>? f' >>? g' >>? h'
    

    which now looks a lot more like our original composition.


    When you read Chapter 14 and learn about monads, you'll discover that monads are just the special functors, like Maybe, for which you can implement join. Further, though here we defined >>? in terms of join, the convention in Haskell is to define >>= (??> for any monad, not just Maybe) directly and then define join in terms of >>=. With Maybe, that looks like

    >>? :: Maybe a -> (a -> Maybe b) -> Maybe b
    Nothing >>? _ = Nothing
    (Just x) >>? f = f x
    
    join :: Maybe (Maybe a) -> Maybe a
    join m = m >>? id
    -- join Nothing = Nothing >>? id = Nothing
    -- join (Just Nothing) = (Just Nothing) >>? id = id Nothing = Nothing
    -- join (Just (Just x)) = (Just (Just x)) >>? id = id (Just x) = Just x