3 people like it.

# recursive to dynamic programming with ycombinator

Dynamic programming is equivalent to recursion + some way to remember the results (as far as I undertand) The y combinator allows to "tie" a previously "untied" recursion, which itself allows to compositionally inject additional steps in the recursion. This allows to go from recursion to dynamic programming in a structured way. This exemple is a bit contrived, as there are no overlapping subproblems, which would be the case in more interesting problem (dtw etc..)

 ``` 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() 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)

### More information

 Link: http://fssnip.net/gh Posted: 8 years ago Author: Nicolas2 Tags: recursion , dynamic programming , ycombinator