2 people like it.
Like the snippet!

From Löb's Theorem to Spreadsheet Evaluation (memoized)

From Löb's Theorem to Spreadsheet Evaluation (memoized), based on http://blog.sigfpe.com/2006/11/from-l-theorem-to-spreadsheet.html

 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:

// From Löb's Theorem to Spreadsheet Evaluation (memoized)
// based on http://blog.sigfpe.com/2006/11/from-l-theorem-to-spreadsheet.html

type seq2<'T> = seq<seq<'T>>

let loeb : seq2<seq2<'T> -> 'T> -> seq2<'T> = fun seqs ->
    let rec g =  
        seq { for fs in seqs ->
                seq { for f in fs -> f g } |> Seq.cache } |> Seq.cache
    g

let value : 'T -> seq2<'T> -> 'T = 
    fun v _ -> v

let nth : (int * int) -> seq2<'T> -> 'T = 
    fun (i, j) cells -> cells |> Seq.item i |> Seq.item j


let cells : seq2<seq2<int> -> int> =
    [[value 1; nth (0, 0)];
     [value 2; fun c -> nth (1, 0) c + nth (0, 1) c];
     [value 3; fun c -> nth (2, 0) c + nth (1, 1) c];
     [value 4; fun c -> nth (3, 0) c + nth (2, 1) c];
     [value 5; fun c -> nth (4, 0) c + nth (3, 1) c];] 
    |> Seq.map Seq.cast 

cells |> loeb |> Seq.toArray
// [|seq [1; 1]; 
//   seq [2; 3]; 
//   seq [3; 6]; 
//   seq [4; 10]; 
//   seq [5; 15] |]

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

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

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

val loeb : seqs:seq2<(seq2<'T> -> 'T)> -> seq2<'T>

Full name: Script.loeb

type seq2<'T> = seq<seq<'T>>

Full name: Script.seq2<_>

val seqs : seq2<(seq2<'T> -> 'T)>

val g : seq<seq<'T>>

val fs : seq<(seq2<'T> -> 'T)>

val f : (seq2<'T> -> 'T)

module Seq

from Microsoft.FSharp.Collections

val cache : source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.cache

val value : v:'T -> seq2<'T> -> 'T

Full name: Script.value

val v : 'T

val nth : i:int * j:int -> cells:seq2<'T> -> 'T

Full name: Script.nth

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 i : int

val j : int

val cells : seq2<'T>

val item : index:int -> source:seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.item

val cells : seq2<(seq2<int> -> int)>

Full name: Script.cells

val c : seq2<int>

val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map

val cast : source:System.Collections.IEnumerable -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.cast

val toArray : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Seq.toArray

Raw view Test code New version

More information

Link:	http://fssnip.net/7T3
Posted:	7 years ago
Author:	NIck Palladinos
Tags:	loeb function , memoization