ljeabmreosn February 2016

Recursive Sequences in F#

Let's say I want to calculate the factorial of an integer. A simple approach to this in F# would be:

let rec fact (n: bigint) =
    match n with
    | x when x = 0I -> 1I
    | _ -> n * fact (n-1I)

But, if my program needs dynamic programming, how could I sustain functional programming whilst using memoization?

One idea I had for this was making a sequence of lazy elements, but I ran into a problem. Assume that the follow code was acceptable in F# (it is not):

let rec facts = 
    seq {
        yield 1I
        for i in 1I..900I do 
            yield lazy (i * (facts |> Seq.item ((i-1I) |> int)))
    }

Is there anything similar to this idea in F#? (Note: I understand that I could use a .NET Dictionary but isn't invoking the ".Add()" method imperative style?)

Also, Is there any way I could generalize this with a function? For example, could I create a sequence of length of the collatz function defined by the function:

let rec collatz n i = 
    if n = 0 || n = 1 then (i+1)
    elif n % 2 = 0 then collatz (n/2) (i+1) 
    else collatz (3*n+1) (i+1)

Answers


TheInnerLight February 2016

If you want to do it lazily, this is a nice approach:

let factorials =
    Seq.initInfinite (fun n -> bigint n + 1I)
    |> Seq.scan ((*)) 1I
    |> Seq.cache

The Seq.cache means you won't repeatedly evaluate elements you've already enumerated.

You can then take a particular number of factorials using e.g. Seq.take n, or get a particular factorial using Seq.item n.


Sid Burn February 2016


At first, i don't see in your example what you mean with "dynamic programming".


Using memorization doesn't mean something is not "functional" or breaks immutability. The important point is not how something is implemented. The important thing is how it behaves. A function that uses a mutable memoization is still considered pure, as long as it behaves like a pure function/immutable function. So using a mutable variables in a limited scope that is not visible to the caller is still considered pure. If the implementation would be important we could also consider tail-recursion as not pure, as the compiler transform it into a loop with mutable variables under the hood. There also exists some List.xyz function that use mutation and transform things into a mutable variable just because of speed. Those function are still considered pure/immutable because they still behave like pure function.


A sequence itself is already lazy. It already computes all its elements only when you ask for those elements. So it doesn't make much sense to me to create a sequence that returns lazy elements.


If you want to speed up the computation there exists multiple ways how to do it. Even in the recursion version you could use an accumulator that is passed to the next function call. Instead of doing deep recursion.

let fact n =
    let rec loop acc x =
        if   x = n 
        then acc * x
        else loop (acc*x) (x+1I)
    loop 1I 1I

That overall is the same as

let fact' n =
    let mutable acc = 1I
    let mutable x   = 1I
    while x <= n do
        acc <- acc * x
        x   <- x + 1I
    acc

As long you are learning functional programming it is a good idea to get accustomed to the first version and learn to understand how looping and recursion relate to each other. But besides learning there isn't a reason why you always should force yourself to always wr

Post Status

Asked in February 2016
Viewed 3,563 times
Voted 9
Answered 2 times

Search




Leave an answer