3 people like it.

# 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) (m : Lazy) : (Tree> * 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>>