Back to Questions
3.2k
views5
comments
Computing probability via recursion
f#functionalclasses

Hi there.
I'm rather new to F# and not very good at functional programming so far, having never used something comparable apart from basic Lisp classes a bunch of years ago.

I was tempted to start learning F# for quite some time when I stumbled upon an article on "The daily WTF", where the guys in the comments where basically argueing pro/contra recursion for a small problem.

The given task was this: (Copied from [link:thedailywtf.com]
George bought a sack of 100 pieces of candy at the store. 90 of the pieces are lemon flavored and ten are cherry flavored. Of the two, George prefers the lemon flavored candies.

Every day George randomly picks a piece of candy out of the bag. If it is lemon flavored, he eats it and puts the bag away for the next day.

But if the candy he chose is cherry flavored, he puts it back in the bag and then randomly picks a candy out of the bag and eats it regardless of the flavor. In other words, he'll only put a piece of candy back at most once per day.

What are the odds that when one piece of candy remains, it will be lemon flavored?

The solution wasn't the problem here, I grabbed a Haskell solution and transformed it to F#. The only thing I wanted to gain was some "writing experience", I didn't care about the problem itself. Now I do have this Haskel-to-F# transformed code and wonder if that's the way it would've been done in the first place. Being right at the start of my learning curve I'd appreciate early feedback, before I get used to "bad" habits.

In other words: This is just a question for comments on the transformation of the given program and asking for obvious pitfalls that I shouldn't repeat in the future.

Thanks in advance,
Ben

Haskell code with memoization (copied from [link:thedailywtf.com]

p :: Int -> Int -> Double
p 0 y = 0
p x 0 = 1
p x y = (py+1)*px*(ps !! (x-1) !! y) + py**2*(ps !! x !! (y-1))
where
(dx, dy) = (fromIntegral x, fromIntegral y)
px = dx / (dx+dy)
py = dy / (dx+dy)
ps = do
y <- [0..]
return [p x y | x <- [0..]]

main = print (p 90 10)

My take on the task in F#:

#light
open System;
open System.Collections.Generic;

let p x y =
let cache = Dictionary<_, _>()

let rec ps x y =
let ok, res = cache.TryGetValue((x,y))
if ok then
res
else
let res =
match x, y with
| 0, _ -> 0.0
| _, 0 -> 1.0
| _ ->
let px = float(x)/float(x+y)
let py = float(y)/float(x+y)
(py+1.0) * px * (ps (x-1) y) + py**2.0 * (ps x (y-1))
cache.[(x,y)] <- res
res
ps x y

print_any (p 90 10)
Console.ReadLine() |> ignore

.

Regarding the style of the recursive solution: you will want to separate the caching from the function logic and then compose the cached function from a generic caching function and your logic solution. Assuming you have a proper function memoize, your function p could look like:

1
2
3
4
5
6
7
8
9
10

let p =
      let ps ps x y =
            match x, y with
            | 0, _ -> 0.0
            | _, 0 -> 1.0
            | _ ->
                  let px = float(x)/float(x+y)
                  let py = float(y)/float(x+y)
                  (py+1.0) * px * (ps (x-1) y) + py**2.0 * (ps x (y-1))
      memoize ps
By on 2/3/2009 3:13 AM ()

Just out of curiosity, how would you write such a definition of memoize?

By on 2/3/2009 8:11 AM ()

Just out of curiosity, how would you write such a definition of memoize?

Like this [:)]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#light
#nowarn "40"

open System.Collections.Generic

module Memo=
    let Cached f=
      let cache=new Dictionary<_,_>()
        fun a -> match cache.TryGetValue a with
                          | true, result -> result
                          | _ -> let result=f a
                                        lock cache (fun () -> cache.[ a ] <- result)
                                        result
    let Cached2 f=
        fun a b -> Cached (fun (a,b) -> f a b) (a,b)

    let CachedRec f=
        let rec r=f (fun a->r a) |> Cached in r
    let CachedRec2 f=
        let rec r=f (fun a b->r a b) |> Cached2 in r
let memoize = Memo.CachedRec2
By on 2/3/2009 11:14 AM ()

It's possible without recursion as well:

1
2
3
4
5

#light

let p x y = x / ((y+1.) * (x+y))

print_any (p 90. 10.)
By on 2/3/2009 3:04 AM ()

The only thing I can see is, that you can calc "py" by "let py = 1.0 - px"

the rest looks fine for me - of course there is not much functional programming going on...

By on 2/3/2009 2:22 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