Generalizing from Parsers

Haskell Reminders

Typeclasses We Already Know

Haskell has what it calls “typeclasses” (similar what some other programming languages call interfaces or traits). We can write functions that are generalized to require that the it works on any type that provides that interface.

Num

• Provides +, -, * and fromInteger.
• Double, Float, Int, Int8, Int16, Int32, Int64, Integer, Rational, Word, Word8, Word16, Word32, Word64
• Being a member of Num also makes you a member of Eq and Show
• Being a member of Num does NOT make you a member of Ord

Eq

• Provides ==, !=
• Supports equality and inequality checks

Ord

• Provides <, etc.
• Totally ordered

Show

• Provides show
• Can be printed as a string

Read

• Provides read
• Can be deserialized from a string (read-in)

etc.

There are many more typeclasses!

What does Read "15" :: Float do?

What else is Parser a like...?

Our type of >>=: is

      >>=: :: Parser a -> (a -> b) -> Parser b

(Note the colon at the end, this is not >>= !!)

What does it remind you of?

      map :: (a -> b) -> [a] -> [b]

So, it'd be cool if we could say

*PicParser> parse (num >>=: (+1)) "42"
43
*PicParser> [1,2,3,4] >>=: (+1)
[2,3,4,5]
*PicParser> Just 17 >>=: (+1)
Just 18
*PicParser> let f = (*3) >>=: (+1)
*PicParser> f 5
16

We can!

Functor, a typeclass for “mapable things”

The Functor typeclass says that if I write a new type, Foble a, I just need to provide an operation

    fmap :: (a -> b) -> Foble a -> Foble b

But the fmap function I write should also satisfy some laws to model our intuitions about “mappable” things:

    fmap id        ≡    id
    fmap (f . g)   ≡   (fmap f) . (fmap g)

(where id is the identity function). Note: another way of thinking about the first of these laws is that fmapping the identity function onto a Foble doesn't change it.

The >>=: operation is just fmap with the arguments reversed.

Examples

The Maybe type is a Functor

*SimpleExpr> fmap (+1) (Nothing)
Nothing
*SimpleExpr> fmap (+1) (Just 17)
Just 18
*SimpleExpr> fmap show (Just 17)
Just "17"

So is the List type

*SimpleExpr> map ( show . (+7) ) [1,2,3,4,5]
["8","9","10","11","12"]
*SimpleExpr> (map show . map (+7)) [1,2,3,4,5]
["8","9","10","11","12"]

So is the being-a-function type!

*SimpleExpr> fmap (*3) (+4) 1
15
*SimpleExpr> fmap show (+4) 1
"5"
*SimpleExpr> ((*3) . (+4)) 1
15
*SimpleExpr> (show . (+4)) 1
"5"

What is the output of the following expression?

fmap (show . (*2) . read) ["1","2","3"]

Alternative, a typeclass for or-like operations;

The Alternative typeclass exists to support Functor types that have an “or”-like or “plus”-like operation. (In mathematical terms, a monoid.)

The requirements for Alternative say that if I write a new type, Foble a that I want to be an Alternative , I need to provide (in addition to fmap) two operations

    empty :: Foble a
    <|>   :: Foble a -> Foble a -> Foble a

But it should also satisfy some laws (specifically the laws of monoids), which are

    empty <|> p      ≡  p
    p <|> empty      ≡  p
    (p <|> q) <|> r  ≡  p <|> (q <|> r)

The Alternative typeclass provides the definitions of some and many that we've been using.

(Technically, an Alternative doesn't just need to already be a Functor, it also needs to be an Applicative, but we'll gloss over that because we don't want to descend too far into the weeds of Haskell .)

Examples

The Maybe type is an Alternative

*SimpleExpr> Nothing <|> Just 17
Just 17
*SimpleExpr> Just 3 <|> Nothing
Just 3
*SimpleExpr> fmap show (Just 17)
Just "17"
*SimpleExpr> Just 3 <|> (Just 4 <|> Just 5)
Just 3
*SimpleExpr> (Just 3 <|> Just 4) <|> Just 5
Just 3

So is the List type

*SimpleExpr> [] <|> [1,2,3,4]
[1,2,3,4]
*SimpleExpr> [1,2,3,4] <|> []
[1,2,3,4]
*SimpleExpr> [1,2,3] <|> ([4,5] <|> [6,7,8])
[1,2,3,4,5,6,7,8]
*SimpleExpr> ([1,2,3] <|> [4,5]) <|> [6,7,8]
[1,2,3,4,5,6,7,8]

And, as you've already seen, our parsing operations are also an instance of Alternative.

Reminder: Our Fundamental Parsing Operations

>>=    :: Parser a ->  (a -> Parser b) -> Parser b
return :: a -> Parser a
fail   :: String -> Parser a

pfail  :: Parser a
<|>    :: Parser a -> Parser a -> Parser a 

get    :: Parser Char

Let's focus on determining some laws for >>= and return.

>>=    :: Parser a ->  (a -> Parser b) -> Parser b
return :: a -> Parser a

Any trivial laws that >>= and return ought to satisfy?

    return x >>= makeP     ≡     makeP x
    p >>= return           ≡     p     
    p1 >>= (\r1 -> makeP2 r1 >>= makeP3)   ≡    (p1 >>= makeP2) >>= makeP3

Discovering Monads

The above laws seem like they might apply to any type t where t Thing “somehow promises a Thing”.

Data structures that support these operations and follow these same basic laws (parsers, maybes, lists, ...) are all known as monads.

Thus, before we had...

    >>=    :: Parser a ->  (a -> Parser b) -> Parser b
    return :: a -> Parser a

and now we have

    >>=    :: (Monad m) => m a -> (a -> m b) -> m b
    return :: (Monad m) => a -> m a

Note: All Monads are functors, but not all functors are monads. Every monad can be a functor because fmap f x is equivalent to x >>= \r -> return (f r), thus every Monad can trivially implement fmap. (Also, every monad can also trivially implement the requirements of Applicative.)

Lists as a Monad

Do these operations make sense for lists? The types would be

    >>=    :: [a] ->  (a -> [b]) -> [b]    
    return :: a -> [a]    

But what would they mean? Idea, let's remember how lists behave as a functor and then decide what >>= ought to do for lists.

*SimpleExpr> [5,10,15] >>=: (\x -> [x,x+1,x+2])
[[5,6,7],[10,11,12],[15,16,17]]
*SimpleExpr> [5,10,15] >>= (\x -> [x,x+1,x+2])
[5,6,7,10,11,12,15,16,17]

Whereas >>=: was like map, >>= is like concatMap.

We can also use >>= for filtering:

*SimpleExpr> [5,10,15] >>= (\x -> if x `mod` 2 == 0 then return x else [])
[10]
*SimpleExpr> [5,10,15] >>= (\x -> if x `mod` 2 == 0 then return x else fail "Moo")
[10]

(Note: in this case if we use fail, it doesn't matter what our failure message actually is; those elements are simply not in the returned list.)

What should return do?

    return x = [x]

Maybe as a Monad

    >>=    :: Maybe a  ->  (a -> Maybe b)  -> Maybe b
    return :: a -> Maybe a

In this case, >>= passes the function through to the thing that we maybe have, or does nothing if we have Nothing:

*SimpleExpr> Just 4 >>= (\x -> if x `mod` 2 == 0 then return x else fail "Moo")
Just 4
*SimpleExpr> Just 7 >>= (\x -> if x `mod` 2 == 0 then return x else fail "Moo")
Nothing
*SimpleExpr> Nothing >>= (\x -> if x `mod` 2 == 0 then return x else fail "Moo")
Nothing

What does return look like in this case?

    return x = Just x

-- MelissaONeill - 03 Mar 2020