3 people like it.
Like the snippet!

The repmin problem

The repmin problem is to replace all elements of a tree of numbers by the minimum element, making only a single pass over the original tree. Repmin is a very ingenious example of Circular Programming.

 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: 
26: 
27: 
28: 
29: 
30: 
31: 
32:

// For more info
// http://www.springerlink.com/content/g74174vvl1861605/
// http://www.haskell.org/haskellwiki/Circular_programming

// Helper functions
let force (value : Lazy<_>) = value.Force()
let lazyMap f l = lazy (f (force l))

// Generic feedback loop function
let trace f input = 
    let rec x = lazy (f input (lazyMap snd x)) in fst (force x)

type Tree<'a> = L of 'a | B of Tree<'a> * Tree<'a>

// Copy the original tree - with patched Leaf nodes
let rec copy (tree : Tree<int>) (m : Lazy<int>) : (Tree<Lazy<int>> * int) = 
    match tree with
    | L a -> (L m, a)
    | B (l, r) ->
         let (l', ml) = copy l m
         let (r', mr) = copy r m
         (B (l', r'), min ml mr)

let repmin t = trace copy t

let rec print tree = 
    match tree with
    | L v -> sprintf "(L %A)" (force v)
    | B (l, r) -> sprintf "(B (%A, %A))" (print l) (print r)

// Example
print (repmin (B (B (L -1, L 2), L 1))) // "(B ((B ((L -1), (L -1))), (L -1)))"

val force : value:Lazy<'a> -> 'a

Full name: Script.force

val value : Lazy<'a>

Multiple items
active recognizer Lazy: Lazy<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.( |Lazy| )

--------------------
type Lazy<'T> = System.Lazy<'T>

Full name: Microsoft.FSharp.Control.Lazy<_>

member System.Lazy.Force : unit -> 'T

val lazyMap : f:('a -> 'b) -> l:Lazy<'a> -> Lazy<'b>

Full name: Script.lazyMap

val f : ('a -> 'b)

val l : Lazy<'a>

val trace : f:('a -> Lazy<'b> -> 'c * 'b) -> input:'a -> 'c

Full name: Script.trace

val f : ('a -> Lazy<'b> -> 'c * 'b)

val input : 'a

val x : Lazy<'c * 'b>

val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd

val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst

type Tree<'a> =
| L of 'a
| B of Tree<'a> * Tree<'a>

Full name: Script.Tree<_>

union case Tree.L: 'a -> Tree<'a>

union case Tree.B: Tree<'a> * Tree<'a> -> Tree<'a>

val copy : tree:Tree<int> -> m:Lazy<int> -> Tree<Lazy<int>> * int

Full name: Script.copy

val tree : Tree<int>

Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

val m : Lazy<int>

val a : int

val l : Tree<int>

val r : Tree<int>

val l' : Tree<Lazy<int>>

val ml : int

val r' : Tree<Lazy<int>>

val mr : int

val min : e1:'T -> e2:'T -> 'T (requires comparison)

Full name: Microsoft.FSharp.Core.Operators.min

val repmin : t:Tree<int> -> Tree<Lazy<int>>

Full name: Script.repmin

val t : Tree<int>

val print : tree:Tree<#Lazy<'b>> -> string

Full name: Script.print

val tree : Tree<#Lazy<'b>>

val v : #Lazy<'b>

val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf

val l : Tree<#Lazy<'b>>

val r : Tree<#Lazy<'b>>

Previous Version Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/4D
Posted:	13 years ago
Author:	Nick Palladinos
Tags:	circular programming , repmin , lazy