100 people like it.

Continuation-Passing Mnemonics

Continuations provide a means whereby heap space can be traded for stack depth (heap space being generally more plentiful than stack depth). They are especially useful where tail recursion is not possible. Here are a couple of simple continuation examples that can be extended to cover more complex scenarios.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 

/// Fibonacci computation using continuations.
/// Something of a continuation classic.
let fib n =
  let rec f n cont =
    match n with
    | 0 -> cont 0
    | 1 -> cont 1
    | n -> 
      f (n-2) (fun n2-> 
        f (n-1) (fun n1->
          cont(n1+n2)))
  f n id


/// Sum of 1-n using continuations.
/// Somewhat simpler to remember.
/// Note: this is only an example,
/// in reality, tail recursion would be 
/// a more appropriate choice here.
let sum1 n =
  let rec f n cont =
    match n with
    | 1 -> cont 1
    | n -> f (n-1) (fun n1->cont(n+n1))
  f n id
val fib : n:int -> int

Full name: Script.fib


 Fibonacci computation using continuations.
 Something of a continuation classic.
val n : int
val f : (int -> (int -> 'a) -> 'a)
val cont : (int -> 'a)
val n2 : int
val n1 : int
val id : x:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.id
val sum1 : n:int -> int

Full name: Script.sum1


 Sum of 1-n using continuations.
 Somewhat simpler to remember.
 Note: this is only an example,
 in reality, tail recursion would be
 a more appropriate choice here.

More information

Link:http://fssnip.net/Z
Posted:13 years ago
Author:Neil Carrier
Tags: continuations , recursion

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.