Buffer with Monoids

Buffer.lhs

Fun with monoids
================

We'll need the monoid library.

> import Data.Monoid

Difference lists
----------------

Difference lists are functions mapping lists to lists. For the
purposes of the type checker, we'll make this an explicit type.

> newtype DiffList a = DL { unDL :: [a] -> [a] }

It is obviously a monoid as `(a -> b)` is a monoid when `b` is a
monoid.

> instance Monoid (DiffList a) where
>   mempty        = DL $ mempty
>   mappend xs ys = DL $ mappend (unDL xs) (unDL ys)

Turn any difference list into a list.

> dlToL :: DiffList a -> [a]
> dlToL x = unDL x []

Pointed functors
----------------

Pointed functors are ones that for any plain ordinary value of type
`a`, we can raise it up to type `f a`.

Notice how that is part of the `Monad` and `Applicative`
specifications through `return` and `pure` respectively.

> class Pointed f where
>   raise :: a -> f a

For instance, any list is pointed as you can have a singleton list of
that value.

> instance Pointed [] where
>   raise x = [x]
  
For instance, any difference list is pointed as you can have a
function that adds the plain ordinary value to the head.
                  
> instance Pointed DiffList where
>   raise x = DL $ \ys -> x:ys

Buffer
------

Spec: A function that will only emit whole lines. E.g.

> ex1 = "foo\n" ++ undefined
> ex2 = "foo \n bar \n" ++ undefined
> ex3 = "foo \n bar" ++ undefined

< buffer ex1  == "foo \n" ++ ⊥
< buffer ex2  == "foo \n bar \n" ++ ⊥
< buffer ex3  == "foo \n" ++ ⊥

> bufferNaive :: String -> String
> bufferNaive = buffer' mempty

> bufferEffic :: String -> String
> bufferEffic = dlToL . buffer' mempty

> buffer' :: (Monoid (f Char), Pointed f) => f Char -> String -> f Char
> buffer' buf []        = buf
> buffer' buf ('\n':xs) = (buf `mappend` raise '\n') `mappend` buffer' mempty xs
> buffer' buf (x   :xs) = buffer' (buf `mappend` raise x) xs

Exercise
--------

Specialise versions of `buffer'` as interpreted by `bufferNaive` and
`bufferEffic` and see what form they take.