3
$\begingroup$

Probably the most common recursion scheme is the catamorphism, or fold. This is a recursion that takes a data type and "deconstructs" it into something else. For example, we can calculate the length of a list using a fold (with Haskell syntax):

length :: [a] -> Int
length xs = foldr 0 (+1) xs

One property of all folds that I've seen is that they look at all elements of the data type. But is there work formalizing recursion schemes that do not look at all elements? That is, they prune some of them away.

If the type of foldr :: (a -> b -> b) -> b -> t a -> b, then the pruning fold would look something like prunefold :: (???) -> (a -> b -> b) -> b -> t a -> b, where ??? is the pruning rule. I can imagine many different possible forms of these pruning rules just for folds, and I imagine other recursion schemes would have even more.

Motivating example 1: We could search a binary search tree using a fold. This fold would perform a depth first search. But this is very inefficient. Instead, we would prefer to have a "pruning rule" that on each iteration removes removes half the tree. This pruning fold gives us the same answer, but reduces the complexity from $O(n)$ to $O(\log n)$.

Motivating example 2: We can express $\pi$ as a sum over an infinite sequence. A standard fold over this sequence would never terminate. But we could use a pruning rule to stop our fold after a certain amount of accuracy has been reached. When used on an infinite data structure, the pruning fold is strictly more powerful.

$\endgroup$
  • $\begingroup$ Hi Mike, Google for "hylomorphism" -- you're looking for the composition of a fold with an unfold. $\endgroup$ – Neel Krishnaswami Jul 15 '13 at 14:11
  • $\begingroup$ @NeelKrishnaswami I've seen hylomorphisms, but I don't see how you could capture either of my examples using one. They still (at least semantically) fully deconstruct and then reconstruct the whole data structure. I want to look at just part of the data structure. $\endgroup$ – Mike Izbicki Jul 15 '13 at 15:46
  • $\begingroup$ @NeelKrishnaswami I see how the second example can be implemented using a hylomorphism (using e.g. Haskell's scan function), but not the speed improvement of the first example. $\endgroup$ – Mike Izbicki Jul 15 '13 at 16:04
4
$\begingroup$

I think my comment was a little cryptic, so let me unpack. The key intuition behind hylomorphisms is that they let you reify the call graph as a data structure. You unfold a datastructure to build a representation of the call graph, and then you fold over the intermediate structure to consume and finish the computation.

Lists are a little misleading, because in a recursive algorithm over a list, the call graph will also form a list. However, in general this will not be the case: the call graph will have a different shape than your input data, and so you'll need to introduce a new datatype to represent it. As an example. here's your binary search example. I'll use Ocaml, since I'm more familiar with it, but it should be fairly easy to transcribe it to Haskell.

First, let's introduce a datatype of binary search trees. We'll just assume they maintain the invariant in a node Node(l, x, r) that the left subnode l contains the elements smaller than x and the right subtree r contains the elements bigger than x.

type tree = Leaf | Node of tree * int * tree

Now, let's introduce a datatype to represent the call graph of a binary search. A binary search will finish with failure if the tree is a Leaf, finish with success if you have a Node whose value is what you're looking for, and keep going otherwise.

We'll represent this with a datatype result that is either a Done b, where b is a boolean with success or failure, or else gives you a Next thunk with a computation which will give you a new result. (In Haskell, you wouldn't need the unit -> 'a thing because all datatypes are lazy.)

We'll split result into a functor resultF, and tie the recursive knot in this datatype explicitly, so that we can easily program the map functional for functor.

type 'a resultF = Done of bool | Next of (unit -> 'a)
type result = Rec of result resultF

let map_resultF f v =
  match v with
  | Done b -> Done b
  | Next thunk -> Next (fun () -> f (thunk()))   

Now, we can define a fold operation for the result type.

(* val fold_result : ('a resultF -> 'a) -> result -> 'a *)
let rec fold_result f (Rec result) =
  f (map_resultF (fold_result f) result)

Here's a function that uses the fold function to force all the Next steps until you get to the boolean final answer.

(* val finish : result -> bool *)
let finish  = 
  fold_result 
    (fun r -> 
       match r with 
       | Done b -> b 
       | Next thunk -> thunk())

We finally get to the interesting part. Here's the unfold operation for the result type:

(* val unfold_result : ('a -> 'a resultF) -> 'a -> result *)
let rec unfold_result f  seed =
  Rec (map_resultF (unfold_result f) (f seed))

Now, you can see how to use an integer and a tree to construct a result:

(* val mem' : int -> tree -> result *)
let mem' x =
  unfold_result
    (fun seed -> 
      match seed with 
      | Leaf -> Done false
      | Node(l, y, r) ->
          if       x < y then Next (fun () -> l)
          else if  x > y then Next (fun () -> r)
          else                Done true)

The really critical is that we're using the unfold to incrementally take the input, and building a result which we use to control the shape of the computation. This is where the pruning is taking place, and you can change it to whatever you like. Also, note that if you want to do something fancy (e.g., use intermediate estimates to control the pruning), you can change the result type to contain it, and update your unfold to compute it.

Finally, you can see the mem function as the fold followed by an unfold, of the result type:

(* val mem : int -> tree -> bool *)
let mem x tree = finish (mem' x tree)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.