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<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 (%s, %s))" (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>>

More information

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