Back to Questions
3.7k
views5
comments
Monads and memoization question
f#monadsmonad

I am trying to understand the best way to memoize while working with monads.

Below I took the identity monad from Matt's posting under [link:cs.hubfs.net]

My question: is this the right way to memoize while working with monads? 

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
33
34
35
36
37
38
39
40
41
42
43
44
45

type Identity<'a> = (unit -> 'a)
let id x = (fun () -> x) : Identity<'a>
let runIdentity (m : Identity<'a>) = m()
let bind m (f: 'a -> Identity<'b>) = f (runIdentity m)
let delay f = (fun () -> runIdentity (f ()))
type IdentityBuilder() =
    member b.Bind(m,f)  = bind m f
    member b.Delay(f) = delay f
    member b.Let(x,f) : Identity<'a> = f x
    member b.Return(x) = id x
    
let identity = new IdentityBuilder()
let memoize (cache: Map<_,_> ref) f = 
    fun x -> 
        match (!cache).TryFind(x) with
        | Some res -> res
        | None -> 
             let res = f x
             cache := (!cache).Add(x,res)
             res
             
let memoizeMonadic (monad:IdentityBuilder) cache f =
    memoize cache (fun x-> monad {return f x})

let square_monad = 
    let cache = ref Map.empty
    memoizeMonadic identity cache (fun x-> x*x)
    
let plus3_monad =
    let cache = ref Map.empty
    memoizeMonadic identity cache (fun x-> x+3)

let square_plus3_monad x =
    identity {
        let! rs = square_monad x
        let! r = plus3_monad rs
        return r
    }
do
    let result1 = runIdentity (square_plus3_monad 4)
    let result2 = runIdentity (square_plus3_monad 4)
    printfn "%A" result1 |> ignore;
    printfn "%A" result2 |> ignore;
    System.Console.ReadLine() |> ignore
.

memoizeMonadic seems to be quite restrictive(only accept IdentifyBuilder).

not sure what you want to achieve

By on 1/5/2010 11:29 PM ()

Good point.

I was trying to something like "Monadic Memoization Mixins" (but without the mix-in concept) ([link:www.cs.utexas.edu]).

But maybe I need to try it on a monad that does something.

By on 1/5/2010 11:59 PM ()

A bit further reading leads me to believe that if I want my memoization to to be held by the state of the monad and if I also want to support recursion, I want to write continuation and state monad that are compatible. I'll post that when it works.

By on 1/6/2010 1:21 PM ()

Here the stateless monadic memoization code. I based it on the state continuation monad, the code is inspired from this posting [link:www.mail-archive.com]

Trying to understand how this monad works, I found this work on monadic reflection by A. Filinsky ([link:www.cs.ioc.ee] It is very interesting.

(By the way, can someone tell me how to post code so that it is readable? )

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

type  csm<'s,'m,'w> = 's -> ('s -> 'm -> 'w) -> 'w

let ret a  = fun s k -> k s a
let bind a f = fun s k -> a s (fun s2 b -> (f b) s2 k)
let get = fun (s:'s) k -> k s s // ret s
let set v = fun _ k -> k v ()
let runCS m = fun s0 -> m s0 (fun _ v -> v)
let runCS2 m = fun s0 -> m s0 (fun s v -> (s,v))

// I don't know if this is correct
let CallCC f  =
    (fun s0 ka -> f (fun a -> (fun s1 kb -> kb a s1) s0 ka))

type CSBuilder() =
    member b.Bind(m,f)  = bind m f
    member b.Return(x) = ret x

let memoize f x = 
    bind get (fun (omap:Map<_,_> option) ->
        let computeAndAdd (toMap:Map<_,_>) =
            bind (f x) (fun v ->
            bind (set (Some (toMap.Add(x,v)))) (fun() ->
            ret v
            ))
        match omap with
        | Some map ->
            let d = map.TryFind x
            match d with
            | None ->
                computeAndAdd map
            | Some v ->
                ret v
        | None ->
            computeAndAdd Map.empty
        )

let csm = new CSBuilder()
let plus1 x = csm { return x+1 }
let mplus1 = memoize2 plus1

let plus x =
    csm {
        let! rs = mplus1 x
        let! r = mplus1 rs
        return r
    }

let plusplus x = 
    csm {
        let! y= plus x
        let! z= plus x
        return z
        }
    
do
    let (map, r) = runCS2 (plusplus 4) None
    printf "%A" map
    System.Console.ReadLine() |> ignore
By on 1/12/2010 12:42 AM ()

(By the way, can someone tell me how to post code so that it is readable? )

I've seen this question a bit lately, so I posted this:

[link:cs.hubfs.net]

By on 1/12/2010 9:25 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper