Selected Programming Techniques

This chapter focuses on functional programming techniques, often used to make functional programs more efficient.

Difference listes

A well known example of program optimization for a program on lists is the reverse-function. The naive implementation with quadratic run time is:

reverse :: [a] -> [a]
reverse []     = []
reverse (x:xs) = reverse xs ++ [x]

Using an accumulator, it is possible to realize a linear algorithm:

reverse :: [a] -> [a]
reverse l = rev l []
 where
  rev :: [a] -> [a] -> [a]
  rev []     ys = ys
  rev (x:xs) ys = rev xs (x:ys)

The second implementation is less intuitive, but much more efficient. The first implementation is based on the induction principle, without introducing an additional parameter, which is used like a kind of stack and reverses the list.

Because of currying, we can see rev also as a function of arity one, which yields a function of type [a] -> [a]. Its type is `rev :: [a] -> ([a] -> [a]). Using this idea, we can also implement rev as follows:

reverse :: [a] -> [a]
reverse l = rev l []
 where
  rev []     = id
  rev (x:xs) = rev xs . (x:)

Now, rev has the same structure as the naive implementation of reverse. id is the value representing the empty list and function composition (.) takes the role of (++). Finally, the one elementary list [x] is represented by the section (x:). So, we replaced the list monoid by the function moniod and optimised efficiency of reverse.

This idea can be expressed within an abstract data type, called difference lists1. Another name, often used for this data structure is functional list, since the list is represented by a function.

import Data.Monoid

newtype DList a = DList ([a] -> [a])

instance Monoid (DList a) where
  mempty                      = DList id
  DList xs `mappend` DList ys = DList (xs . ys)

The implementation of mappend is non-recursive and hence takes constant run time, which then results in a linear algorithm for reverse.

Like in the implementation of reverse it is always possible, to convert a difference list into a common list, by simply applying the difference list to the empty list.

fromDList :: DList a -> [a]
fromDList (DList xs) = xs []

Intuitively, a difference list is a function, that holds elements and is able to put this elements in front of it missing argument. A common list can therefore be converted into a difference list by

toDList :: [a] -> DList a
toDList xs = DList (xs ++)

Now we can now re-implement the reverse-function, to make it more visible that we are using difference lists.

reverse :: [a] -> [a]
reverse l = fromDList (rev l)
 where
  rev []     = mempty
  rev (x:xs) = rev xs `mappend` toDList [x]

This implementation uses the (++)-function only within toDList and only with the one elementary list [x]. Hence, its run-time is similar to the implementation using the accumulator technique. But it is as elegant, as the naive implementation of reverse.

The application of difference lists is not restricted to reverse. Whenever one constructs a list, e.g. while traversing a tree, difference lists are a good choice. As an example, we consider a function, collecting node labels in infix order. The naive implementation uses the result of the recursive call as left argument of (++) and in worst-case (unbalanced tree to the left) we obtain qudratic run-time in the number of nodes in the tree.

With difference lists we can list the labels in linear time with respect to the number of nodes inside the tree:

data Tree a = Empty
            | Node (Tree a) a (Tree a)
 deriving Eq

infixLabels :: Tree a -> [a]
infixLabels = fromDList . labels
 where
  labels Empty          = mempty
  labels (Branch l x r) =
    labels l `mappend` toDList [x]
             `mappend` labels r

The functions toDList and fromDList are inverse monoid-isomorphisms to each other (simple proof by induction). Therefore, it is possible to translate every program using lists and only using monoid operations into an equivalent program using difference lists, without changing its behaviour.

Unfortunately, we cannot use difference list in every program operating on lists. For instance, we cannot check whether a give DList is empty, without converting it into the common list form.

nullDL :: DList a -> Bool
nullDL (DList dl) = null (dl [])

We have to apply the DList to the empty list and can perform the empty test afterwards. Otherwise, we cannot see the top-level constructor. For this problem, we can still find a solution, by storing the size of the list in an additional Int-parameter for DList, which would also allow us, to define a length function for DLists. However, this trick is restricted to simple information. We cannot access the elements within the difference list and can therefore not implement functions like map- or concat on difference lists, as the following try shows:

mapDL :: (a -> b) -> DList a -> DList b
mapDL f (DList dl) = DList (\l -> ???)

We are not able to apply f to the elements of dl, without converting dl into a common list. This also holds for many other list functions.

However, we will later introduce some advanced techniques, which will allow the definition of map and concat for difference lists.

Another typical example for tree traversals, which produces lists, are show-functions. The Show-class contains the following functions2:

class Show a where
  show :: a -> String
  show x = shows x ""

  showsPrec :: Int -> a -> ShowS

The type ShowS and the function shows are defined as follows:

type ShowS = String -> String

shows :: Show a => a -> ShowS
shows = showsPrec 0

The type ShowS represents strings as difference lists and shows behaves like show, but with difference lists. The function showsPrec gets an additional parameter, which can be used to respect precedences, to avoid superflous brackets. For simplicity, we will ignore this parameter in the following.

Using the type ShowS, we can convert tree data structures into strings in linear time with respect to the size of the tree.

instance Show a => Show (Tree a) where
  showsPrec _ Empty          = showString "Empty"
  showsPrec _ (Branch l x r) = showString "Branch " .
                               showParen (l/=Empty) (shows l) .
                               showChar ' ' . shows x . showChar ' ' .
                               showParen (r/=Empty) (shows r)

Similar to the type DList we use function composition instead string concatenation.

The function showString relates to the function toDList and constructs from a String a corresponding value of type ShowS.

showString :: String -> ShowS
showString = (++)

Similar, showChar behaves for single characters

showChar :: Char -> ShowS
showChar = (:)

and showParen constructs parentheses around a value within ShowS, if the flag passed is True.

showParen :: Bool -> ShowS -> ShowS
showParen True  s = showChar '(' . s . showChar ')'
showParen False s = s

All these functions are defined in the Prelude.

Continuations

As an example for the monad Maybe we defined a data type

data Expr = Num Int
          | Expr :+: Expr
          | Expr :/: Expr

and a function

eval :: Expr -> Maybe Int

The result of eval was Nothing, if a division by zero occurred during the evaluation.

Let's consider the evaluation of the following expression:

Num 4 :/: (Num 1 :+: Num (-1)) :+: Num 4

The pass through the tree representing the data structure can be visualised by the following picture.

Bild von einem Baumdurchlauf

Bild von einem Baumdurchlauf

If the value Nothing occurs, we cancel the walk through the tree. For instance the right arguemtn of the top-level :+:-node is not evaluated, because the left arguemnt fails.

The value Nothing occurs somewhere in the tree and is sucessively passed to the root of the tree. The eval-function or more precise, the bind operator of the Maybe-Monad testes every result, whether it is Nothing and then produces Nothing as its result. If the first Nothing occures very deep in the tree, this passing of Nothing to the root may be a bit inefficient. Is it possible to stop the whole computation instead of passing Nothing values up to the root?

A solution for this is called Continuation Passing Style (CPS) and we define a CPS version of our eval-function. A function in CPS takes a function as an additional argument, the so called continuation, which represents the whole further computation. In CPS, the type of the eval-function changes to:

evalCPS :: Expr
        -> (Int -> Maybe Int)
        -> Maybe Int

Since the continuation represents the further computation, we can simply apply it in the success case. For the leafs in our expressions we get:

evalCPS (Num x) k = k x

To evaluate multiple expressions successively and combine the results, we nest the continuations and evaluate the second expression within the continuation of the first expression.

evalCPS (e1 :+: e2) k =
  evalCPS e1 (\v1 -> evalCPS e2 (\v2 -> k (v1 + v2)))

With this pattern, it is now possible, to stop the computation immediately, if a division by zero occurs. We can ignore the continuation and directly return Nothing.

evalCPS (e1 :/: e2) k =
  evalCPS e1 (\v1 ->
   evalCPS e2 (\v2 ->
    if v2 == 0 then Nothing else k (v1 / v2)))

This program does not contain any pattern matching against Nothing. Hence, no values are successively passed up to the root of the expression. In the error case, the program directly returns Nothing.

An alternative implementation of the last rule, computes the divisor first, which optimises the code such that the dividend is not evaluated, if the divisor evaluates to zero:

evalCPS (e1 :/: e2) k =
  evalCPS e2 (\v2 ->
   if v2 == 0 then Nothing
    else evalCPS e1 (\v1 -> k (v1 / v2)))

The computation of evalCPS with the expression from above, requires an additional continuation of type Int -> Maybe Int, which should by Just.

    ghci> let zero = Num 1 :+: Num (-1)
    ghci> let expr = (Num 4 :/: zero) :+: Num 4
    ghci> evalCPS expr Just
    Nothing

We evaluate the computation step-by-step:

      evalCPS expr Just
    = evalCPS ((Num 4 :/: zero) :+: Num 4) Just
    = evalCPS (Num 4 :/: zero) (\x ->
       evalCPS (Num 4) (\y -> Just (x+y)))
    = evalCPS zero (\b ->
       if b==0 then Nothing
        else evalCPS (Num 4) (\a ->
         evalCPS (Num 4) (\y -> Just ((a/b)+y))))
    = evalCPS (Num 1 :+: Num (-1)) (\b ->
       if b==0 then Nothing
        else evalCPS (Num 4) (\a ->
         evalCPS (Num 4) (\y -> Just ((a/b)+y))))
    = evalCPS (Num 1) (\c ->
       evalCPS (Num (-1)) (\d ->
        if (c+d)==0 then Nothing
         else evalCPS (Num 4) (\a ->
          evalCPS (Num 4) (\y ->
           Just ((a/(c+d))+y)))))
    = evalCPS (Num (-1)) (\d ->
       if (1+d)==0 then Nothing
        else evalCPS (Num 4) (\a ->
         evalCPS (Num 4) (\y ->
          Just ((a/(1+d))+y))))
    = if (1+(-1))==0 then Nothing
       else evalCPS (Num 4) (\a ->
        evalCPS (Num 4) (\y ->
         Just ((a/(1+d))+y)))
    = Nothing

The result Nothing is directly returned and not passed through any tree structure.

The presented function evalCPS is more efficient than the function eval in the Maybe-Monad, but less readable. As a next step we define a monadic variant of CPS on Maybe-values.

Inspired by the type of evalCPS, we define the follwoing data type:

newtype CMaybe r a = CMaybe ((a -> Maybe r) -> Maybe r)

This type relates to the result type of evalCPS, where Int is generalized to the type parameters and a. Values of type CMaybe can be converted into common Maybe-values by applying them to the continuation Just:

fromCMaybe :: CMaybe a a -> Maybe a
fromCMaybe (CMaybe ca) = ca Just

In the converting step, the type parameters r and a get unified. Before the conversion, the type r usually stays polymorphic.

As a next step we define an instance of Monad for CMaybe r:

instance Monad (CMaybe r) where
  return x = CMaybe (\k -> k x)

  CMaybe ca >>= f = CMaybe (\k ->
    ca (\x -> let CMaybe cb = f x in cb k))

The implementation of return passes the argument to the continuation and the implementation of bind nests the computation of the second argument into the continuation of the first one. As a consequence the type of the result is of type Maybe b, but the argument is of type a. In contrast to the pure Maybe-Monad (>>=) is defined without pattern matching.

We proof the monad laws, independently of the result type of the continuation. Again for readability, we ignore then newtype constructor:

      return x >>= f
    = (\k -> k x) >>= f
    = (\k' -> (\k -> k x) (\x' -> f x' k'))
    = (\k' -> (\x' -> f x' k') x)
    = (\k' -> f x k')
    = f x

      ca >>= return
    = (\k -> ca (\x -> return x k))
    = (\k -> ca (\x -> (\k' -> k' x) k))
    = (\k -> ca (\x -> k x))
    = (\k -> ca k)
    = ca

      (ca >>= f) >>= g
    = (\k -> ca (\x -> f x k)) >>= g
    = \k' -> (\k -> ca (\x -> f x k))
              (\y -> g y k')
    = \k' -> ca (\x -> f x (\y -> g y k'))
    = \k' -> ca (\x -> (\k ->
                 f x (\y -> g y k)) k')
    = \k' -> ca (\x -> (f x >>= g) k')
    = ca >>= \x -> f x >>= g

Both, the implementation of the monad operations and the proofs of the monad laws are independent of the result type of the continuation Maybe r. Later, we will define further continuation monads with different result types, for which, this implementation as well as the proofs are identical.

Now we define an instance of class MonadPlus for CMaybe , by lifting the corresponding operations from the type Maybe,

instance MonadPlus (CMaybe r) where
  mzero = CMaybe (\_ -> mzero)

  CMaybe ca `mplus` CMaybe cb =
    CMaybe (\cont -> ca cont `mplus` cb cont)

Again, we proof the relevant laws, ignoring the newtype constructors.

      mzero >>= f
    = (\_ -> mzero) >>= f
      \k -> (\_ -> mzero) (\x -> f x k)
    = \k -> mzero
    = mzero

      (ca `mplus` cb) >>= f
    = \k -> (ca `mplus` cb) (\x -> f x k)
    = \k -> (\k' -> ca k' `mplus` cb k') (\x -> f x k)
    = \k -> ca  (\x -> f x k) `mplus` cb (\x -> f x k)
    = \k -> (\k' -> ca (\x -> f x k')) k `mplus` (\k' -> cb (\x -> f x k')) k
    = \k -> (ca >>= f) k `mplus` (cb >>= f) k
    = ca >>= f `mplus` cb >>= f

Hence, the monad CMaybe fulfils the distributivity law, in contrast to the Maybe-Monad. The reason is, that the whole remaining computation is passed down with the continuation. Hence, it is not necessary to choose in the implementation of mplus. If one branch fails, the other one is chosen, even if we branch or fail in dependence of the monadic result.

As a consequence, we can use the monad for search and back tracking.

    ghci> let a = return False `mplus` return True
    ghci> let b = a >>= guard
    ghci> b :: Maybe ()
    Nothing
    ghci> fromCMaybe b
    Just ()

Now, we can define the monadic implementation of eval

eval :: MonadPlus m => Expr -> m Int
eval (Num x) = return x
eval (a :+: b) =
  do x <- eval a
     y <- eval b
     return (x+y)
eval (a :/: b) =
  do y <- eval b
     guard (y/=0)
     x <- eval a
     return (x/y)

Executing the program within the CMaybe-Monad, evaluates our expression similar to the function evalCPS.

The Maybe-Monad is not the only continuation based monad. Replacing Maybe by DList within the definition of CMaybe, results in a continuation based list monad, which we will inspect later.

We saw, that our implementation fulfils the following law:

    (a `mplus` b) >>= f  =  (a>>=f) `mplus` (b>>=f)

although mplus for the monad Maybe does not fulfil it. The Maybe instance instead fullfills the law:

    return x `mplus` a  =  return x

which is a law, that reminds us to a catch within an error-monad: only if the left argument fails, the rigth argument is executed. Such a function is often also called orElse and sometimes useful.

Can we define a function orElse for CMaybe, which fulfils the law:

    return x `orElse` a  =  return x

This is possible, with the following code:

orElse :: CMaybe a a -> CMaybe a a -> CMaybe r a
CMaybe ca `orElse` CMaybe cb =
  CMaybe (\k -> (ca Just `mplus` cb Just) >>= k)

This implementation passes Just as continuation to both alternatives and combines both results by the function mplus from the Maybe-monad. The result is again converted into continuation passing style and applied to a given continuation k. In the type of orElse the type parameter of the arguments r gets unified with the type parameter a by applying ca and cb to the continuation Just :: a -> Maybe a.

By changing from cps, to normal style and back again, we obtain a kind of encapsulation of the computation of the first parameter of orElse.

The catch property of orElse can easily be shown:

      return x `orElse` a
    = (\k -> ((return x) Just `mplus` a Just)
              >>= k)
    = (\k -> ((\k' -> k' x) Just `mplus` a Just)
              >>= k)
    = (\k -> (Just x `mplus` a Just) >>= k)
    = (\k -> Just x >>= k)
    = (\k -> k x)
    = return x

Hence, orElse behaves similar to mplus in the Maybe-monad:

    ghci> let a = return False `orElse` return True
    ghci> fromCMaybe (a >>= guard)
    Nothing

Using this methode, we can lift Maybe values to CMaybe values.

toCMaybe :: Maybe a -> CMaybe r a
toCMaybe a = CMaybe (\k -> a >>= k)

Here, the function toCMaybe is a monad homomorphismus, since the following laws hold:

    toCMaybe (return x)  =  return x
    toCMaybe (a >>= f)   =  toCMaybe a >>= toCMaybe . f

The proof is again simple:

      toCMaybe (return x)
    = \k -> return x >>= k
    = \k -> k x
    = return x

      toCMaybe (a >>= f)  =
    = \k -> (a >>= f) >>= k
    = \k -> a >>= (\w -> f w >>= k) -- Ass. >>= 
    = \k1 -> a >>= (\x -> (f x >>= k1)) -- alpha-Konversion
    = \k1 -> a >>= (\x -> (\z -> \k2 -> f z >>= k2) x k1)
    = \k1 -> (\k -> a >>= k) (\x -> (\z -> \k2 -> f z >>= k2) x k1)
    = (\k -> a >>= k) >>= \z -> \k2 -> f z >>= k2
    = toCMaybe a >>= \z -> toCMaybe (f z)
    = toCMaybe a >>= toCMaybe . f

Within the proofs we use the left identity and an associativity law from the underlying Maybe-monad.


  1. The name difference list comes from logic programming - an analogy we don't discuss any further here.

  2. In addition to the presented functions, the class Show provides a functions showList :: Show a => [a] -> String. By this function, it is possible to modify the list representation of a given data type. The default implementation presents lists with square brackets and separates the elements with commas. For the data type Char, however, we want a representation of lists of Char as a String. Therefore, in the Char-instance, the function showlist is overwritten, such that lists of characters are represented in the well known string representation.