recursive to dynamic programming with ycombinator

 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: 

//simple factorial
let rec factorial n = 
    if n = 0I then 1I else n * factorial (n-1I)
factorial 10I


//tied and untied factorial - equivalent to simple recursion
let rec factorialu factorial' n = 
    if n = 0I then 1I else n * factorial' (n-1I)

let rec y f x = f  (y f ) x
y factorialu 10I 

//dynamic programming
open System.Collections.Generic
let memoize (d:Dictionary<_,_>) f n = 
   if d.ContainsKey n then d.[n] 
   else System.Threading.Thread.Sleep(10) // to slow down
        d.Add(n, f n)
        d.[n]

let factorialdp  = 
    let d =  Dictionary<bigint, bigint>()
    fun n ->  
        y (factorialu >> fun f n -> memoize d f n ) n
    
#time
factorialdp 15I  //242 ms

factorialdp 15I  //0 ms

val factorial : n:System.Numerics.BigInteger -> System.Numerics.BigInteger

Full name: Script.factorial

val n : System.Numerics.BigInteger

val factorialu : factorial':(System.Numerics.BigInteger -> System.Numerics.BigInteger) -> n:System.Numerics.BigInteger -> System.Numerics.BigInteger

Full name: Script.factorialu

val factorial' : (System.Numerics.BigInteger -> System.Numerics.BigInteger)

val y : f:(('a -> 'b) -> 'a -> 'b) -> x:'a -> 'b

Full name: Script.y

val f : (('a -> 'b) -> 'a -> 'b)

val x : 'a

namespace System

namespace System.Collections

namespace System.Collections.Generic

val memoize : d:Dictionary<'a,'b> -> f:('a -> 'b) -> n:'a -> 'b

Full name: Script.memoize

val d : Dictionary<'a,'b>

Multiple items
type Dictionary<'TKey,'TValue> =
  new : unit -> Dictionary<'TKey, 'TValue> + 5 overloads
  member Add : key:'TKey * value:'TValue -> unit
  member Clear : unit -> unit
  member Comparer : IEqualityComparer<'TKey>
  member ContainsKey : key:'TKey -> bool
  member ContainsValue : value:'TValue -> bool
  member Count : int
  member GetEnumerator : unit -> Enumerator<'TKey, 'TValue>
  member GetObjectData : info:SerializationInfo * context:StreamingContext -> unit
  member Item : 'TKey -> 'TValue with get, set
  ...
  nested type Enumerator
  nested type KeyCollection
  nested type ValueCollection

Full name: System.Collections.Generic.Dictionary<_,_>

--------------------
Dictionary() : unit
Dictionary(capacity: int) : unit
Dictionary(comparer: IEqualityComparer<'TKey>) : unit
Dictionary(dictionary: IDictionary<'TKey,'TValue>) : unit
Dictionary(capacity: int, comparer: IEqualityComparer<'TKey>) : unit
Dictionary(dictionary: IDictionary<'TKey,'TValue>, comparer: IEqualityComparer<'TKey>) : unit

val f : ('a -> 'b)

val n : 'a

Dictionary.ContainsKey(key: 'a) : bool

namespace System.Threading

Multiple items
type Thread =
  inherit CriticalFinalizerObject
  new : start:ThreadStart -> Thread + 3 overloads
  member Abort : unit -> unit + 1 overload
  member ApartmentState : ApartmentState with get, set
  member CurrentCulture : CultureInfo with get, set
  member CurrentUICulture : CultureInfo with get, set
  member DisableComObjectEagerCleanup : unit -> unit
  member ExecutionContext : ExecutionContext
  member GetApartmentState : unit -> ApartmentState
  member GetCompressedStack : unit -> CompressedStack
  member GetHashCode : unit -> int
  ...

Full name: System.Threading.Thread

--------------------
System.Threading.Thread(start: System.Threading.ThreadStart) : unit
System.Threading.Thread(start: System.Threading.ParameterizedThreadStart) : unit
System.Threading.Thread(start: System.Threading.ThreadStart, maxStackSize: int) : unit
System.Threading.Thread(start: System.Threading.ParameterizedThreadStart, maxStackSize: int) : unit

System.Threading.Thread.Sleep(timeout: System.TimeSpan) : unit
System.Threading.Thread.Sleep(millisecondsTimeout: int) : unit

Dictionary.Add(key: 'a, value: 'b) : unit

val factorialdp : (System.Numerics.BigInteger -> System.Numerics.BigInteger)

Full name: Script.factorialdp

val d : Dictionary<bigint,bigint>

type bigint = System.Numerics.BigInteger

Full name: Microsoft.FSharp.Core.bigint

val f : (System.Numerics.BigInteger -> System.Numerics.BigInteger)