Abstraction Revisited

What's good about separating interface & implementation?

• Users don't have to worry about how things work, and we can hide implementation details
• We can swap out the implementation for a different one (assuming users aren't allowed to sneak a peek into the implementation)
• Users are “protected from hurting themselves/others” by abusing/misusing the internals of the implementation.

What are some downsides?

• Less concrete
• People who care about “what is going on inside” can't see it as easily.
• Some things can't be done because the interface doesn't support it (even though the underlying implementation could)
• The tools used to create the abstraction may also need to be understood.

Wiki Extra: Abstraction in our Parser Code

Think back to our parsing code. Given the provided base operations (from which everything else is built):

fail   :: String -> Parser a
return :: a -> Parser a
get    :: Parser Char
<|>    :: Parser a -> Parser a -> Parser a
>>=    :: Parser a ->  (a -> Parser b) -> Parser b

and our Secret internal representation:

newtype Parser a = ParsingFunction (String -> ParseResult a)
data ParseResult a = Success a String
                   | Failure String

Can you write getTwoChars ?

Can you write a parser that gets two characters?

twochars :: Parser (Char, Char)
twochars = get >>= (\c1 -> (get >>= \c2 -> return (c1, c2)))

Can you write put ?

Can you write a parser that ``puts back'' new never-before-seen characters into the input?

put :: Char -> Parser ()
put c = ParsingFunction (\input -> Success () (c : input))

Can you write ifErrorIs ?

Can you write a parser that makes a decision based on the error message of a previous parser?

ifErrorIs :: Parser a -> (String -> Parser a) -> Parser a
ifErrorIs (ParsingFunction pFn) errHandler = ParsingFunction newParser
    where newParser input = 
              case pFn input of
                  Success v rest -> Success v rest
                  Failure msg    -> let ParsingFunction qFn = errHandler msg
                                    in  qFn input

Monads etc. Revisited

Consider this code for the list monad, what does it do?

   [1,2,3] >>= (\i -> ([7,11,23] >>= (\j -> return (i+j))))

It's equivalent to:

    concatMap (\i -> (concatMap (\j -> [i+j]) [7,11,23])) [1,2,3]

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

Prelude> map (\x -> x + 7) [1,2,3]
[8,9,10]
Prelude> map (\x -> [x + 7]) [1,2,3]
[[8],[9],[10]]
Prelude> concat [[8],[9],[10]]
[8,9,10]
Prelude> map (\x -> [x + 7, x+17]) [1,2,3]
[[8,18],[9,19],[10,20]]
Prelude> concat [[8,18],[9,19],[10,20]]
[8,18,9,19,10,20]
Prelude> concat (map (\x -> [x + 7, x+17]) [1,2,3])
[8,18,9,19,10,20]
Prelude> concatMap (\x -> [x + 7, x+17]) [1,2,3]
[8,18,9,19,10,20]

which is equivalent to

    concat (map (\i -> (concat (map (\j -> [i+j]) [7,11,23]))) [1,2,3])

[8,12,24,9,13,25,10,14,26]

What does this do?

    [1,2,3] >>= (\i -> ([7,11,23] >>= (\j -> if isEven i then [i+j] else [])))

[9,13,25]

We could also add filtering by writing:

   [1,2,3] >>= (\i -> ([7,11,23] >>= (\j -> if isEven i then return (i+j) else empty)))

The actual type of <+> in our parser library was not

The Applicative Typeclass

Using the >>= (“and then”) operator is a bit ugly. We could solve this with another typeclass, in this case Applicative which provides a new operator, <*>. For lists, this operator is:

   <*> :: [a -> b] -> [a] -> [b]

  pure :: Applicative t => a -> t a
  <*>  :: Applicative t => t (a -> b) -> t a -> t b

  pure :: a -> [a]
  pure x = [x]

  return :: a -> [a]
  return x = [x]

With this, we can write:

Prelude> [(+)] <*> [1,2,3] <*> [7,11,23]
[8,12,24,9,13,25,10,14,26]
Prelude> [(+),(-),(*)] <*> [1,2,3] <*> [7,11,23]
[8,12,24,9,13,25,10,14,26,-6,-10,-22,-5,-9,-21,-4,-8,-20,7,11,23,14,22,46,21,33,69]

List Comprehensions

Rather than use the >>= (“and then”) explicitly, wouldn't it be better to have some nice syntactic sugar for it?

Prelude> [i+j | i <- [1,2,3], j <- [7,11,23]]
[8,12,24,9,13,25,10,14,26]
Prelude> isEven x = x `mod` 2 == 0
Prelude> [i+j | i <- [1,2,3], j <- [7,11,23], isEven i]
[9,13,25]

This would still mean the code above, using >>= but be much more pleasant to write!

Generalized list comprehensions?

The “and then” operation is general, so we could write:

Prelude> Just 2 >>= (\i -> (Just 11 >>= (\j -> if isEven i then return (i+j) else empty)))
Just 13
Prelude> Nothing >>= (\i -> (Just 11 >>= (\j -> if isEven i then return (i+j) else empty)))
Nothing

and

PicParser> p = num >>= (\i -> (num >>= (\j -> if isEven i then return (i+j) else empty)))
PicParser> parse p "2 11"
13
PicParser> parse p "1 11"
*** Exception: <input>:1:5 -- Oh noes

So does it make sense to be able to say:

[i+j | i <- Just 2, j <- Just 11, isEven i]

or

myparser = [i+j | i <- num, j <- num, isEven i]

do Notation

Writing

do var <- p
    q

p >>= (\var -> q)

And

do AAA
    BBB
    CCC

do AAA
    do BBB
        CCC

In do notation, our code becomes:

do i <- [1,2,3]
   j <- [7,11,23]
   return (i+j)

and

do i <- Just 2
   j <- Just 11
   return (i+j)

and

myparser = do i <- num
              j <- num
              return (i+j)

Interactive Session Code from Class

Section 2

You'll recall writing code like this (i.e., using <+> in the homework...

*SimpleExpr> :t num      -- num is the number parser
num :: Parser Integer
*SimpleExpr> p = num <+> num
*SimpleExpr> parse p "40 2"
(40,2)

*SimpleExpr> p = num >>= (\n1 -> num)
*SimpleExpr> parse p "40 2"
2
*SimpleExpr> p = num >>= (\n1 -> (num >>= (\n2 -> return 0)))
*SimpleExpr> parse p "40 2"
0
*SimpleExpr> p = num >>= (\n1 -> (num >>= (\n2 -> return (n1,n2))))
*SimpleExpr> parse p "40 2"
(40,2)
*SimpleExpr> p = num >>= (\n1 -> (num >>= (\n2 -> return (n1+n2))))
*SimpleExpr> parse p "40 2"
42

*SimpleExpr> p = return (+) <*> num <*> num
*SimpleExpr> parse p "40 2"
42
*SimpleExpr> p = return (+1) <*> num
*SimpleExpr> parse p "41"
42
*SimpleExpr> ourstar l r = l >>= (\f -> r >>= \v -> return (f v))
*SimpleExpr> p = return (+1) `ourstar` num
*SimpleExpr> parse p "41"
42

*SimpleExpr> Just 40 >>= (\n1 -> (Just 2 >>= (\n2 -> return (n1+n2))))
Just 42
*SimpleExpr> Just 40 >>= (\n1 -> (Just 2 >>= (\n2 -> return (n1,n2))))
Just (40,2)
*SimpleExpr> [40] >>= (\n1 -> ([2] >>= (\n2 -> return (n1+n2))))
[42]
*SimpleExpr> p = num >>= (\n1 -> (num >>= (\n2 -> return (n1+n2))))
*SimpleExpr> parse p "xxx"
*** Exception: <input>:1:1 -- <number> expected
*SimpleExpr> parse p "40 x"
*** Exception: <input>:1:4 -- <number> expected
*SimpleExpr> Nothing >>= (\n1 -> (Just 2 >>= (\n2 -> return (n1+n2))))
Nothing
*SimpleExpr> [] >>= (\n1 -> ([2] >>= (\n2 -> return (n1+n2))))
[]
*SimpleExpr> [1,2,3,4] >>= (\n1 -> ([100,200,300] >>= (\n2 -> return (n1+n2))))
[101,201,301,102,202,302,103,203,303,104,204,304]
*SimpleExpr> [1,2,3,4] >>= (\n1 -> ([100,200,300] >>= (\n2 -> return (n1,n2))))
[(1,100),(1,200),(1,300),(2,100),(2,200),(2,300),(3,100),(3,200),(3,300),(4,100),(4,200),(4,300)]
*SimpleExpr> [n1+n2 | n1 <- [1,2,3,4], n2 <- [100,200,300]]
[101,201,301,102,202,302,103,203,303,104,204,304]
*SimpleExpr> [n1+n2 | n1 <- [1,2,3,4], n2 <- [100,200,300], (n1+n2) `rem` 2 == 0]
[102,202,302,104,204,304]
*SimpleExpr> [1,2,3,4] >>= (\n1 -> ([100,200,300] >>= (\n2 -> if (n1+n2) `rem` 2 == 0 then return (n1+n2) else empty)))
[102,202,302,104,204,304]
*SimpleExpr> [(n1,n2) | n1 <- [1,2,3,4], n2 <- [100,200,300], (n1+n2) `rem` 2 == 0]
[(2,100),(2,200),(2,300),(4,100),(4,200),(4,300)]
*SimpleExpr> [1,2,3,4] >>= (\n1 -> ([100,200,300] >>= (\n2 -> if (n1+n2) `rem` 2 == 0 then return (n1,n2) else empty)))
[(2,100),(2,200),(2,300),(4,100),(4,200),(4,300)]

*SimpleExpr> [(n1+n2) | n1 <- [1,2,3,4], n2 <- [100,200,300], (n1+n2) `rem` 2 == 0]
*SimpleExpr> [(n1+n2) | n1 <- Just 40, n2 <- Just 2, (n1+n2) `rem` 2 == 0]

<interactive>:46:18: error:
    &#8226; [ long message -- Monad comprehensions aren't a thing. ]

ghci -XMonadComprehensions
GHCi, version 8.8.2: https://www.haskell.org/ghc/  :? for help
Prelude> [(n1+n2) | n1 <- Just 40, n2 <- Just 2, (n1+n2) `rem` 2 == 0]
Just 42
Prelude> 

*SimpleExpr> do { n1 <- [1,2,3,4]; n2 <- [100,200,300]; if (n1+n2) `rem` 2 == 0 then return (n1+n2) else empty }
[102,202,302,104,204,304]
*SimpleExpr> p = do { n1 <- num; n2 <- num; if (n1+n2) `rem` 2 == 0 then return (n1,n2) else empty }
*SimpleExpr> parse p "40 2"
(40,2)
*SimpleExpr> parse p "40 1"
*** Exception: <input>:1:5 -- No parse (via pfail)
*SimpleExpr> p = do { n1 <- num; n2 <- num; return (n1,n2); }
*SimpleExpr> parse p "40 1"
(40,1)
*SimpleExpr> p = do { n1 <- num; _ <- text "whoa"; n2 <- num; return (n1,n2); }
*SimpleExpr> parse p "40 whoa 2"
(40,2)
*SimpleExpr> p = do { n1 <- num; text "whoa"; n2 <- num; return (n1,n2); }
*SimpleExpr> parse p "40 whoa 2"
(40,2)

Finding More Monads

The code in the Pic2PS assignment looked like this:

   doElems ::  [Element] -> State -> (PostScriptCode, State)
   
   doElems []             state = (PostScript.noCode, state)
   doElems (elem : elems) state = let (ps1, state')  = doElem  elem  state  
                                      (ps2, state'') = doElems elems state' 
                                  in  (ps1 ++ ps2, state'')

How could we refactor this code to use a (new, custom) Monad (in broad strokes). What would the monadic version of the above code look like?

   doElems ::  [Element] -> PicST PostScriptCode
   doElems []             = return PostScript.noCode
   doElems (elem : elems) = do ps1 <- doElem elem  
                               ps2 <- doElems elems 
                               return (ps1 ++ ps2)

   import Control.Monad

   newtype PicST a = STfn (State -> (a, State))

   instance Functor PicST where
   -- fmap :: (a -> b) -> PicST a -> PicST b
   -- fmap f (STfn sfn) = STfn mappedFn
   --      where mappedFn state = let (v, state') = sfn state
   --                             in  (f v, state')
   --
      fmap = liftM    -- a Haskell builtin that uses Monad operations

   instance Applicative PicST where
      pure  = return  -- a Haskell builtin that uses Monad operations
      (<*>) = ap      -- a Haskell builtin that uses Monad operations

   instance Monad PicST where
      return v = STfn (\state -> (v, state))
      (>>=) (STfn f) mkSTfn = STfn combined
           where combined state = let (v, state') = f state 
                                      STfn g      = mkSTfn v
                                  in  g state'

-- MelissaONeill - 05 Mar 2020