From CSULA CS Wiki
Jump to: navigation, search

Contents

Running a recursive function on a recursion engine

factorial is the prototypical recursive function.

factorial n 
   | (n==0) = 1
   | otherwise = n * (factorial (n-1))

Like many recursive functions factorial has the following form.

recursiveFunction x
  | termCond x = termFn x
  | otherwise = reduceFn (mapFn x) (recursiveFunction (wayAheadFn x))

These are the correspondances.

termCond: (n==0). The termination condition is to stop when n is 0.
termFn: 1. The termination function always returns 1.
mapFn : n. The map function takes the input and converts it to something to be used later by the reduce function. In this case the conversion is just the identity.
wayAheadFn : n-1. The way-ahead function converts the input into the form to be passed to the recursive call. In this case, subtract 1.
reduceFn : n * (factorial (n-1)). The reduce function applies a function to (a) what the mapFn left and (b) what the recursive call returned. In this case the function is multiplication.

We would like to make the recursiveFunction template above available so that one can define a recursive function by providing the components functions.

One way to do that is to nest the recursiveFunction template within a context into which we can plug in the various functions.

recursionEngine termCond termFn reduceFn mapFn wayAheadFn = 
  recursiveFunction
  where recursiveFunction y
           | termCond y = termFn y
           | otherwise = reduceFn (mapFn y) (recursiveFunction (wayAheadFn y))

Alternatively:

recursionEngine termCond termFn reduceFn mapFn wayAheadFn = 
  let recursiveFunction y
           | termCond y = termFn y
           | otherwise = reduceFn (mapFn y) (recursiveFunction (wayAheadFn y))
  in recursiveFunction 

In either of these formulations the recursiveFunction template performs the recursion using the functions passed to the recursionEngine.

Using this recursion engine, factorial would look like this.

factorial' = 
  recursionEngine  
     (==0)     -- The termination condition
     (\_ -> 1) -- Return 1
     (*)       -- Performs the multiplication of (n * factorial (n-1)).
     id        -- This keeps the n for the multiplication above.
     (+(-1))   -- This generates (n-1) for the next recursive call.
               -- Can't write just (-1), which is taken as a value, 
               -- or ((-)1), which is taken as the function (\x -> 1 - x).

zip example

Here's an example of converting zip from traditional recursion to using the recursion engine.

This is the traditional definition of zip.

zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x, y) : (zip xs ys)

Since zip takes two arguments and the recursion engine expects to operate on one argument we have to package the two arguments together into a single bundle. A simple way to do that is to put the two arguments in a tuple. Here's what zip would look like if we did it that way.

zipPair ([], _) = []
zipPair (_, []) = []
zipPair ((x:xs), (y:ys)) = (x, y) : (zipPair (xs, ys))
> :t zipPair
zipPair :: ([t1], [t2]) -> [(t1, t2)]

zipPair takes a pair of lists and produces a list of pairs. We could always define myZip to call zipPair.

myZip xs ys = zipPair (xs, ys)

Now we can extract the pieces of zipPair and pass them to the recursionEngine.

zip' xs ys =
   recursionEngine
      (\(x, y) -> null x || null y)  -- termCond. Terminate if either list is []
      (\_ -> [])                     -- termFn. If we terminate return []
      (:)                            -- reduceFn. Rebuild the list
      (\(x:_, y:_) -> (x, y))        -- mapFn. Create a pair from the heads.
      (\(_:xs, _:ys) -> (xs, ys))    -- wayAheadFn. The recursion operates on the tails.
      (xs, ys)

zip' has the same type as zip.

> :t zip'
zip' :: [a1] -> [a2] -> [(a1, a2)]

GCD example

Here's an example of converting the greatest-common-divisor function from traditional recursion to the use of the recursion engine.

This is a traditional gcd algorithm. I'm calling it gcd_1 to distinguish it from the gcd that's exported by the Prelude.

gcd_1 x y
  | x `mod` y == 0 = y
  | otherwise = gcd_1 y (x `mod` y)
> :t gcd_1
gcd_1 :: (Integral a) => a -> a -> a

Since the recursion engine only works on functions that take a single parameter, let's convert gcd_1 into a function of 1 parameter. We could use a tuple, but for practice, let's create a data type to hold the two pieces.

data GCD_Package = GCD_Package Integer Integer deriving (Show)

The creates a data type GCD_Package, which stores two Integer values. In this case we are using the type name as a constructor. Recall that other constructor names can be used.

Here is the same function as gcd_1 but using the GCD_Package.

gcd_2 (GCD_Package x y)
  | x `mod` y == 0 = y
  | otherwise = gcd_2 (GCD_Package y (x `mod` y))
> :t gcd_2
gcd_2 :: GCD_Package -> Integer

What are the components.

termCond:   x `mod` y == 0   
termFn:     Return y
reduceFn:   After the call to gcd_2 we simply return the result. 
            No additional processing is done.
mapFn:      No mapfn because we don't have to produce anything for the reduceFn.
wayAheadFn: GCD_Package y (x `mod` y). This is the argument passed to
            the recursive call of gcd_2.

Let's make well-defined functions out of these and plug them into the recursionEngine.

gcd_3 = 
   recursionEngine 
      (\(GCD_Package x y) -> x `mod` y == 0)            -- termCond
      (\(GCD_Package x y) -> y)                         -- termFn
      (\_ gcd -> gcd)                                   -- reduceFn       
      id                                                -- mapFn
      (\(GCD_Package x y) -> GCD_Package y (x `mod` y)) -- wayAheadFn
               
> :t gcd_3
gcd_3 :: GCD_Package -> Integer

Except for the reduceFn, each of the other functions takes one argument. In this case that argument is (GCD_Package x y).

The reduceFn is different. It takes two arguments. The first is what was produced by the mapFn; the second is what was returned from the recursive call. The recursionEngine makes the recursive call for you. You don't have to do it explicitly. You just have to write the wayAheadFn, which generates the argument to the recursive call. And you have to write the reduceFn which processes the result of the recursive call along with the result of the mapFn.

Tail recursion

In the gcd algorithm the reduceFn does nothing except pass back the result of the recursive call. The mapFn also does nothing since the reduceFn never looks at what it produces. Algorithms with this property are called tail recursive. The term implies that the last thing the algorithm does is to make a recursive call. When the recursive call completes, the result is just passed back.

Since tail recursive algorithms have no need for either a mapFn or a reduceFn we can write a tailRecursionEngine without them. The wayAheadFn does all the real work.

tailRecursionEngine termCond termFn wayAheadFn = 
  tailRecursiveFn
  where tailRecursiveFn y
           | termCond y = termFn y
           | otherwise = (tailRecursiveFn (wayAheadFn y))

The tailRecursionEngine is like the recursionEngine except that it has no reduceFn and no mapFn.

Here's how the gcd algorithm would be expressed in terms of the tailRecursionEngine.

gcd_4 = 
  tailRecursionEngine 
      (\(GCD_Package x y) -> x `mod` y == 0)            -- termCond
      (\(GCD_Package x y) -> y)                         -- termFn
      (\(GCD_Package x y) -> GCD_Package y (x `mod` y)) -- wayAheadFn
> :t gcd_4
gcd_4 :: GCD_Package -> Integer

> gcd_4 (GCD_Package 33 36)
3

Tracing tail recursion

It's often useful to trace the sequence of values generated during the tail recursion process. Instead of simply applying the wayAheadFn over and over again, one can also keep track of those values. Let's define a function trace that applies another function f, our wayAheadFn, to a starting input over and over.

trace f x = x : trace f (f x)

For example,

> take 10 (trace (*2) 1)
[1,2,4,8,16,32,64,128,256,512]

In fact, Haskell already has such a trace function available. It's called iterate.

> take 10 (iterate (*2) 1)
[1,2,4,8,16,32,64,128,256,512]

Let's trace gcd, i.e., apply iterate to the wayAheadFn. To make the results easier to see, instead of GCD_Package, we'll use a simple pair.

> take 10 (iterate (\(x, y) -> (y, (x `mod` y))) (15,39))
[(15,39),(39,15),(15,9),(9,6),(6,3),(3,0),(0,*** Exception: divide by zero

We got a divide by zero exception when we attempted to take 3 `mod` 0.

To avoid that let's define myMod and try again.

myMod _ 0 = 0
myMod x y = mod x y
> take 10 (iterate (\(x, y) -> (y, (x `myMod` y))) (15,39))
[(15,39),(39,15),(15,9),(9,6),(6,3),(3,0),(0,0),(0,0),(0,0),(0,0),]

A utility function that's useful in this conext this is takeUntil. takeUntil is like takeWhile except:

  1. It takes values until its argument function holds rather than while its argument function holds.
  2. It returns not only a list of values but also the value for which the argument function first holds.

It can be defined as follows.

takeUntil termCond (x:xs) 
  | termCond x = (x, [])
  | otherwise = (z, x:zs) where (z, zs) = takeUntil termCond xs  

Or, equivalently

takeUntil termCond (x:xs) 
   | termCond x = (x, [])
   | otherwise = let (z, zs) = takeUntil termCond xs in (z, x:zs)
> :t takeUntil
takeUntil :: (a -> Bool) -> [a] -> (a, [a])

> takeUntil (> 10) [1 .. ]
(11,[1,2,3,4,5,6,7,8,9,10])

takeUntil solves the problem we saw above of getting an exception when we attempt to apply the wayAheadFn when the termination condition holds.

Applying takeUntil with both the termCond and the wayAheadFn from gcd produces this result.

> takeUntil (\(x, y) -> x `mod` y == 0) (iterate (\(x, y) -> (y, (x `mod` y))) (15, 39))
((6,3),[(15,39),(39,15),(15,9),(9,6)])

The pair (6, 3) satisfies the termCond; the list [(15,39),(39,15),(15,9),(9,6)] contains the sequence of pairs generated by the wayAheadFn from the starting point (15,39) that precede (6, 3).

Tail recursion as iteration

As the preceding shows, tail recursion is really iteration disguised as recursion.

  • The wayAheadFn is the body of the iterative loop.
  • The argument (in this example (GCD_Package x y)) is a package that contains (all) the variables used in the loop.
  • The termCond looks at the variables and determines when to stop.
  • The termFn looks at the variables and constructs an answer. In this case it just picks one of the variables.

This suggests the following definition for a tailRecursionEngine with trace.

tailRecursionEngineTrace termCond termFn wayAheadFn x = 
   (termFn termValue, termValue, list)
   where (termValue, list) = takeUntil termCond (iterate wayAheadFn x)

To illustrate, let's define yet another version of gcd. Again we'll use pairs instead of GCD_Package.

gcd_5 x y = 
   tailRecursionEngineTrace 
      (\(x, y) -> x `mod` y == 0)    -- termCond
      (\(x, y) -> y)                 -- termFn
      (\(x, y) -> (y, (x `mod` y)))  -- wayAheadFn
      (x, y)              
> gcd_5 15 39
(3,(6,3),[(15,39),(39,15),(15,9),(9,6)])

The result returned is a triple:

(<function value>, <value terminating the iteration>, <list of preceding values>)

This suggests another formulation for the tailRecursionEngine itself.

tailRecursionEngine termCond termFn wayAheadFn x = 
   termFn (fst (takeUntil termCond (iterate wayAheadFn x)))

Equivalently:

tailRecursionEngine termCond termFn wayAheadFn x = 
   termFn . fst $ takeUntil termCond (iterate wayAheadFn x)

In other words, iterate the wayAheadFn (the body of the loop) until the termCond holds. Then apply the termFn to extract the result.

Applying gcd_4 with this definition of the tailRecursionEngine produces the same answer as before.

> gcd_4 15 39
3

Rather than rely on takeUntil, we can do this more directly by defining iterateUntil. iterateUntil applies the wayAheadFn to its argument until the termCond holds. It also checks to see if the termCond holds on the argument as initially given. iterateUntil returns the value for which termCond first holds.

iterateUntil termCond wayAheadFn x = 
  head (dropWhile (not . termCond) (iterate wayAheadFn x))

Or equivalently

iterateUntil termCond wayAheadFn = 
  head . (dropWhile (not . termCond)) . (iterate wayAheadFn)
Except that the parameters are reversed iterateUntil is really the old familiar do-until
 do <body>
 until <termCond>

The tailRecursionEngine can be defined in terms of iterateUntil. The tailRecursionEngine simply applies the termFn to the result returned by iterateUntil.

tailRecursionEngine termCond termFn wayAheadFn x = termFn (iterateUntil termCond wayAheadFn x)

Or equivalently,

tailRecursionEngine termCond termFn wayAheadFn   = termFn . iterateUntil termCond wayAheadFn

Or, expanding iterateUntil

tailRecursionEngine termCond termFn wayAheadFn  = 
   termFn . head . (dropWhile (not . termCond)) . (iterate wayAheadFn)

Tail recursion, Haskell, and efficiency

Tail recursion is usually considered more efficient that standard recursion. With tail recursion there is no need to keep a stack, which must be unwound when the recursion ends.

But since Haskell is lazy, tail recursion is not always more efficient than standard recursion.

The recursionEngine as a combination of map and reduce

We just saw that we can give an iterative description of tail recursion. This section shows how to give an iterative description of standard recursion.

Think about how the recursionEngine works. It does four things.

  1. It repeatedly calls the wayAheadFn until it finds a value for which the termCond holds.
  2. In the process it leaves behind a trail of values produced by applying the mapFn to the values for which the termCond did not hold.
  3. It applies the termFn to the value for which the termCond holds.
  4. It uses foldr to apply the reducFn to the list of mapped values from step 2. It uses the result from step 3 as the starting point.

(The tailRecursionEngine also does 1 and 3, but it doesn't do 2 or 4.)

Given takeUntil and iterate, we can define recursionAsMapReduce as follows.

recursionAsMapReduce termCond termFn reduceFn mapFn wayAheadFn x =
   let (y, ys) = takeUntil termCond (iterate wayAheadFn x)
   in foldr reduceFn (termFn y) (map mapFn ys)

Or equivalently

recursionAsMapReduce termCond termFn reduceFn mapFn wayAheadFn x =
    foldr reduceFn (termFn y) (map mapFn ys)
    where (y, ys) = takeUntil termCond (iterate wayAheadFn x)

The let or where expression iterates the wayAheadFn until termCond holds. It also captures the value for which termCond holds along with a list of the previously generated values.

The foldr expression first maps the mapFn to the list captured as the second element of the tuple in the let or where portion. Then it repeatedly applies the reduceFn to those values, starting with the value produced by applying the termFm to the value for which the termCond held.

Using recursionAsMapReduce we have defined recursion as a sequence of two iterative processes: iterate and foldr.

Alternative formulation

We can let the first iteration—that done by takeUntil—do more of the work. Let's define mapUntil so that it does not only what takeUntil does, but it also applies the mapFn to the values left behind.

mapUntil termCond mapFn (x:xs) 
 | (termCond x) = (x, [])
 | otherwise = (z, (mapFn x):zs) where (z, zs) = (mapUntil termCond mapFn xs) 

Or, equivalently:

mapUntil termCond mapFn (x:xs) 
  | (termCond x) = (x, [])
  | otherwise = let (z, zs) = (mapUntil termCond mapFn xs) in (z, (mapFn x):zs)

Now recursionAsMapReduce can be defined as follows.

recursionAsMapReduce termCond termFn reduceFn mapFn wayAheadFn x =
   let (y, ys) = mapUntil termCond mapFn (iterate wayAheadFn x)
   in foldr reduceFn (termFn y) ys

Or, equivalently

recursionAsMapReduce termCond termFn reduceFn mapFn wayAheadFn x =
  foldr reduceFn (termFn y) ys
  where (y, ys) = mapUntil termCond mapFn (iterate wayAheadFn x) 
  

The let or where portion still does the first iteration process. But now it also does the mapping. The foldr then does the second iteration process. It applies the termFn to the value found by termCond and uses that as the starting point when it applies the reduceFn to what mapUntil set up for it.

factorial using recursionAsMapReduce

We can define factorial using recursionAsMapReduce.

factorial = 
      recursionAsMapReduce
           (==0)          -- termCond
           (\_ -> 1)      -- termFn
           (*)            -- reduceFn
           id             -- mapFn
           (\n -> n-1)    -- wayAheadFn                

The functions are the same as we used when defining factorial using the recursionEngine.

Let's look at how the execution works. Suppose we call

> factorial 5

Substituting (==0) as the termCond, id as the mapFn, and (\n -> n-1) as the wayAheadFn we generate

> mapUntil (==0) id (iterate (\n -> n-1) 5)

First, iterate repeatedly applies the function it gets as its first argument to its second argument, generating and infinite list. For example:

> take 9 (iterate (\n -> n-1) 5)
[5,4,3,2,1,0,-1,-2,-3]

Since Haskell is lazy, the list elements aren't generated until they are needed. Therefore they are generated only until (==0), the termCond, holds.

Since the mapFn is id, the list of returned elements is the same as the list of elements generated until termCond holds.

This is what we get.

> mapUntil (==0) id (iterate (\n -> n-1) 5)
(0,[5,4,3,2,1])

Next, substituting (\_ -> 1) for termFn, (*) for reduceFn, and [5,4,3,2,1] for ys we call

> foldr (*) ((\_ -> 1) 0) [5,4,3,2,1]

First of all, ((\_ -> 1) 0) returns 1 as the foldr starting element.

Then we use foldr to repeatedly apply the reduceFn to the mapped list and the starting element. So we are making this call.

> foldr (*) 1 [5,4,3,2,1]
120

Multiple recursive calls

The recursionEngine works well for functions that make a single recursive call. What about functions that make multiple recursive calls. quicksort is an example.

quicksort [] = []
quicksort (x:xs) = (quicksort smaller) ++ (x: (quicksort larger))
   where smaller = [y | y <- xs, y <= x]
          larger = [y | y <- xs, y > x]

The problem we face is that for each recursive call to quicksort, two additional recursive calls are made: one to sort the smaller elements and one to sort the larger elements.

One solution is for the recursiveFn of the recursionEngine to map itself over a list of elements instead of calling itself on just one.

Here are the original recursionEngine and an extendedRecursionEngine. The differences are indicated in italics.

recursionEngine termCond termFn reduceFn mapFn wayAheadFn x = 
   recursiveFn x
   where recursiveFn y
             | termCond y = termFn y
             | otherwise = reduceFn (mapFn y) (recursiveFn (wayAheadFn y))
extendedRecursionEngine termCond termFn reduceFn mapFn wayAheadFn x = 
    recursiveFn x
    where recursiveFn y
             | termCond y = termFn y
             | otherwise = reduceFn (mapFn y) (map recursiveFn (wayAheadFn y))

The only difference between the extendedRecursionEngine and the original recursionEngine is that the recursive call is map recursiveFn (wayAheadFn y) instead of recursiveFn (wayAheadFn y).

As far as using the extendedRecursionEngine is concerned

  1. the wayAheadFn must return a list of elements instead of just a single element—although there is nothing to prevent the list from being a singleton. It may even be an empty list, which will end the recursion without relying on termCond.
  2. the reduceFn must now expect its second argument to be a list of results.

Given this extendedRecursionEngine we can define quicksort as follows.

quicksort =      
   extendedRecursionEngine
      null        -- Stop on the empty list.
      id          -- If we get an empty list return it.

                  -- The reduceFn expects a list of two sorted
                  -- lists. It concatenates them with x in between.
      (\x [smaller, larger]-> smaller ++ (x:larger))
      head        -- Save the head for the reduce step.

                  -- The wayAheadFn generates a list of two lists: the 
                  -- elements smaller than or equal to the head and those larger.
      (\(x : xs) -> [[y | y <- xs, y <= x], [y | y <- xs, y >  x]])

Multiple recursive calls when processing trees

Suppose we define a Tree data type that allows multiple children.

data Tree a = Node a [Tree a] | EmptyTree deriving (Show, Eq)

How might we write a function to find the height of a tree? Here's the traditional approach.

height EmptyTree = 0
height (Node _ subtrees) = 1 + maximum (0:(map height subtrees))

Notice that although height is recursive—the recursion occurs when height is mapped onto the children—there is no clause to end the recursion. (The clause for EmptyTree is never called if the argument Tree is not empty.) But the recursion terminates anyway. How does that happen?

If a Tree has no children, the recursion will be mapped over an empty list of children. Since the list is empty, that ends the recursion. That's also the reason maximum is applied to a list with a pre-pended 0. If the recursive call is mapped to an empty list of children, the result will be an empty list.

How would we write height using the extendedRecursionEngine?

First let's define an accessor that retrieves the list of children.

children (Node _ subtrees) = subtrees

Now we can define height as follows.

height = 
   extendedRecursionEngine
      (\tree -> tree == EmptyTree)  -- termCond and termFn are used only 
      (\_ -> 0)                     -- for the EmptyTree.
      (\_ heights ->                -- The reduceFn ignores what the mapFn 
          1 + maximum (0:heights))  -- function generates and simply adds 1 to 
                                    -- the maximum of the heights of the children.
      id                            -- Ignore the value at the Node.
      children                      -- Do recursion on all the children.
> height (Node 1             -- Manually formatted
               [Node 11 
                     [Node 111 [], 
                      Node 112 []
                     ], 
                Node 12 []
               ]
         )
3
> height EmptyTree
0

Making the extended recursion engine iterative

We can't linearlize an algorithm with multiple recursive calls in the body. But we can separate the expansion phase—the use of the wayAheadFn from the reduce phase—the use of the reduceFn.

extendedRecursionEngine termCond termFn reduceFn mapFn wayAheadFn x = 
   reduceTree reduceFn termCond termFn mapFn (buildTree termCond wayAheadFn x)

First we use buildTree to build out the tree. Then we use reduceFn to reduce it to a value.

To build a tree, we need a Tree data type.

data Tree a = Node a [Tree a] deriving (Show, Eq)

Note that we don't need an EmptyTree constructor since we won't have any null Trees. A node without children is indicated by an empty list of children, not through the use of an EmptyTree.

Now we can define buildTree.

buildTree termCond wayAheadFn x =
   buildIt x
   where buildIt x
           | termCond x = Node x []
           | otherwise = Node x (map builtIt (wayAheadFn x))

Note that the Tree we build holds the original value that was used by the wayAheadFn as the value of the Node of the built Tree. We do not apply the mapFn to it yet.

reduceTree reduceFn termCond termFn mapFn tree =
   reduce tree
   where  
      reduce (Node value children)
            | termCond value = termFn value
            | otherwise = reduceFn (mapFn value) (map reduce children)    
      

reduceTree applies the reduceFn to two arguments. The first is the mapFn applied to the original value at that point in the expansion. The second is the list of results from the recursive calls.

Here's how it would apply to quicksort.

quicksort = 
   extendedRecursionEngine 
       null                                 -- Terminate on an empty list
       id                                   -- If we have an empty list that's the answer.
       (\ x [smaller, larger] ->            -- The reduceFn. smaller and larger are 
             smaller ++ (head xs : larger)) -- both sorted. (head xs) is between them in value.
       id                                   -- The mapFn is the identity.   
       (\(x : xs) ->                        -- The wayAheadFn splits the list into two sublists:
             [[y | y <- xs, y <= x],        --   elements less than or equal to the head
              [y | y <- xs, y >  x]])       --   elements greater than the head.
> quicksort [6, 2, 4, 5, 7, 8, 6, 1]
[1,2,4,5,6,6,7,8]

This really hasn't accomplished much. The reduceTree function is nearly identical to the original extendedRecursionEngine. The only difference is that reduceTree assumes that the children are already expanded.