Making Recursion More Systematic

Ad-hoc recursion

We can easily define a recursive function to add all items in a sequence.

scala> def addAll (xs: Seq[Int]): Int = if (xs.isEmpty) 0 else xs.head + (addAll (xs.tail))
addAll: (xs: Seq[Int])Int

scala> addAll(List(1,2,3))
res0: Int = 6

We can also define a higher-order function to apply another suitable function to each item of a sequence.

scala> def myMap[T, U](f: (T) => U)(xs: Seq[T]): List[U] = 
     |   if (xs.isEmpty) Nil else f(xs.head) :: myMap(f)(xs.tail)
myMap: [T, U](f: T => U)(xs: Seq[T])List[U]

scala> myMap(2 * (_: Int))(1 to 3)
res6: List[Int] = List(2, 4, 6)

Same thing without recursion

This method and other, similar ones are predefined on sequences:

override def foldRight[B](z: B)(f: (A, B) => B): B = this match {
  case Nil => z
  case x :: xs => f(x, xs.foldRight(z)(f)) // not tail-recursive
}

We can use it to express addAll

scala> (1 to 3).foldRight(0)(_ + _)
res7: Int = 6

or myMap

scala> def myNonRecMap[T, U](f: (T) => U)(xs: Seq[T]): List[U] = xs.foldRight(Nil : List[U])((x,ys)=> f(x)::ys)
myMap: [T, U](f: T => U)(xs: Seq[T])List[U]

scala> myNonRecMap((_: Int) * 2)(List(1,2,3))
res15: List[Int] = List(2, 4, 6)

Some initial explorations of the Sieve of Eratosthenes

We can write similar functions to perform other operations that involve some or all items in a list. For example, we can try to compute the list of primes using the Sieve of Eratosthenes. Lets start with some explorations toward this end. The predefined Seq.filter method comes in handy:

scala> (_: Seq[Any]) filter (_: Any => Boolean)
res18: (Seq[Any], Any => Boolean) => Seq[Any] = <function2>

Exercise: express filter in terms of foldRight.

scala> (2 to 100).filter(_ % 2 != 0)
res21: Seq.Projection[Int] = Range(3, 5, 7, 9, ...)

scala> res21 filter (_ % 3 != 0)
res22: Seq.Projection[Int] = Range(5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...)

scala> res22 filter (_ % res22.first != 0)
res23: Seq.Projection[Int] = Range(7, 11, 13, 17, 19, 23, 29, 31, 37, ...)

Note how an iteration pattern emerges: in each step, we eliminate multiples of the first element of the current sequence. The successive first elements themselves are the primes. So:

scala> def primes(xs: Seq[Int]): List[Int] = if (xs isEmpty) Nil else xs.head :: primes(xs filter (_ % xs. first != 0))
primes: (xs: Seq[Int])List[Int]

scala> primes(2 to 100)
res0: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)

To see the actual steps, just add a println in the right place:

scala> def primes(xs: Seq[Int]): List[Int] = if (xs isEmpty) Nil else { println(xs); xs.head :: primes(xs filter (_ % xs.head != 0)) }
primes: (xs: Seq[Int])List[Int]

It will now print the remaining candidates after each recursive step. Correctness proof: structural induction on the list.

Same thing without recursion

Let's try this:

scala> def primes(xs: Seq[Int]): List[Int] = xs.foldRight(Nil: List[Int])((y, ys) => { println(ys);  y :: (ys filter (_ % y != 0)) })
primes: (xs: Seq[Int])List[Int]

So this works, but unlike the ad-hoc recursive version above, it requires one step for each original list item instead of one step for each resulting prime! That is not so good. (With foldLeft, you would have a harder time building the result list.) 

It turns out that fold is not powerful enough to express the required pattern of recursion. Fold is a factory function for catamorphisms (http://en.wikipedia.org/wiki/Catamorphism), which break down the data structure step-by-step to produce a result. (I hope our resident classics major will help with the Greek here. The last time I studied Greek myself was at this public school http://goo.gl/s0IF founded in 1604 by Jesuits.) We will instead define an anamorphism (http://en.wikipedia.org/wiki/Anamorphism), which builds up a data structure from a seed and a function applied successively. The factory function for anamorphisms is

scala> def unfoldRight[A, B] (g: B => Option[(A, B)]) (b: B): List[A] = 
               g(b) match { 
                 case Some((a, b1)) => a :: unfoldRight(g)(b1)
                 case None => Nil 
               } 
unfoldRight: [A,B](g: (B) => Option[(A, B)])(b: B)List[A]

Here, b is the seed and g is the step-by-step generator, which uses the predefined Option to produce a pair consisting of the next item and the next seed. While fold requires you to process each item in the underlying list, unfold recurses over the result of applying function g to the seed, b1. This gives you a lot more power, as we will see below. (Btw, Option is a much cleaner alternative to using null, and you are required to use it in this class from now on. http://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare)

We can now define a simple range generator as an anamorphism:

scala> def iToj(i: Int, j: Int) = unfoldRight((x: Int) => if (x <= j) Some(x, x + 1) else None)(i)
iToj: (i: Int,j: Int)List[Int]
scala> iToj(1,10)
res39: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

We can also define identity (on lists) and map as anamorphisms (both of these can easily be defined as catamorphisms, too):

scala> unfoldRight((xs:List[Any]) => if (xs isEmpty) None else Some(xs head, xs tail))(_) 
res22: (List[Any]) => List[Any] = <function1>
scala> res22 (List(1, 4, 2, 7))
res24: List[Any] = List(1, 4, 2, 7)

scala> def mapAsAna[A,B](f: A => B) = unfoldRight((xs: Seq[A]) => if (xs isEmpty) None else Some(f (xs head), xs tail))(_)
mapAsAna: [A,B](f: (A) => B)(Seq[A]) => List[B]
scala> mapAsAna((_:Int) * 2)(1 to 10)
res35: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

And finally:

scala> def primes(ys: Seq[Int]) = unfoldRight((xs: Seq[Int]) => if (xs isEmpty) None else Some(xs head, xs filter (_ % xs.head != 0)))(ys) 
primes: (ys: Seq[Int])List[Int]

Yay! The beauty is that you get to filter the candidate list before each new iteration, so this behaves exactly like the original ad-hoc recursive version.

Tail recursion

For convenience, this unofficial version is defined outside of the List class.

scala> def reduceLeft(f:(Int,Int)=>Int)(xs:List[Int]):Int = xs match {
     | case Nil => throw new UnsupportedOperationException("Nil.reduceLeft")
     | case x :: Nil => x
     | case x :: y :: xs => reduceLeft(f)(f(x,y)::xs) 
     | }
reduceLeft: (f: (Int, Int) => Int)(xs: List[Int])Int

scala> reduceLeft(_+_)((1 to 10).toList)
res1: Int = 55

In the recursive case, it applies f to the first two items and then itself to the list where the first two items are replaced by the result of applying f. That list has one item less, so we eventually reach the one-item base case.

Note how reduceLeft is tail-recursive! After evaluating the actual argument expressions (f and f(x,y)::xs), the very last thing is the recursive call. This allows for automatic tail-call optimization or for conversion of the function to be reimplemented using iteration.

By contrast, reduceRight is not tail-recursive because the recursive call happens somewhere in the middle (buried in the evaluation of the actual arguments):

  case x :: xs => f(x, xs reduceRight f)

For more details, please take a look at this excellent article on the subject


especially the section entitled Evaluation order considerations, which also discusses lazy evaluation and infinite structures.

Finally, note that many common operations can be implemented non-recursively as folds, including map and filter. (Fold is much more flexible than reduce because its result type is not limited to the item type of the list.)

Some final thoughts

Why not simply use ad-hoc recursion? Because that makes it considerably harder to reason about your code. For general operations such as map, fold, unfold, etc., you can prove general laws, which you can then apply to special cases. For ad-hoc recursion, you need to come up with your own, specific proof.

Why bother with this formal stuff at all? Because it provides a solid foundation for the higher-level structures we build on top, and because it trains our minds to think in a certain way and develop an intuition for flaws in those structures.

As usual, I am very interested in your reactions.

References

Comments