CODEWITHSUNDEEP
f#sequence
Matěj Pokorný
Matěj Pokorný

Reputation: 17845

Create sequence based on previous value

I'm learning F# (second day O:-)) and I want to create Collatz sequence, where is every value computed based on previous one. I know, ho to do it in C#

public static void Main(string[] args)
{
    Console.WriteLine(string.Join(", ", collatz(13)));
}

static IEnumerable<int> collatz(int n)
{
    while (n != 1)
    {
        yield return n;

        if (n % 2 == 0)
            n /= 2;
        else
            n = 3 * n + 1;
    }

    yield return 1;
}

or how to create array like that in F#

let rec collatz = function
    | 1 -> [ 1 ]
    | n when n % 2 = 0 -> n::collatz (n / 2)
    | n -> n::collatz (3 * n + 1)

collatz 13 |> Seq.map string |> String.concat ", " |> printfn "%s"

but don't figure out sequence solution...

Upvotes: 4

Views: 397

Answers (4)

Joel Mueller
Joel Mueller

Reputation: 28745

You can do it pretty concisely using Seq.unfold...

let collatzSeq = Seq.unfold <| function 
    | 1 -> Some(1, -1) 
    | -1 -> None 
    | n when n % 2 = 0 -> Some(n, n / 2) 
    | n -> Some(n, 3 * n + 1)

Upvotes: 7

kaefer
kaefer

Reputation: 5741

let collatz n =
    let nr = ref n
    seq{
        while (!nr > 1) do
            yield !nr
            if !nr % 2 = 0 then 
                nr := !nr / 2 
            else 
                nr := 3 * !nr + 1 }
collatz 13
// val it : seq<int> = seq [13; 40; 20; 10; ...]

For a pretty faithful translation of your imperative C# code, you'd need to provide for mutation; as a ref cell or a mutable binding. You can therefore use a sequence expression, and mutation - but preferably recursion.

You can also combine the recursive solution with the concept of memoisation. A dictionary facilitates the retrieval of values already computed, stopping the recursion.

let memoRec f =
    let d = new System.Collections.Generic.Dictionary<_,_>()
    let rec g x =
        match d.TryGetValue x with
        | true, res -> res
        | _ -> let res = f g x in d.Add(x, res); res
    g

let collatzRec =
    memoRec (fun f n -> seq{
        if n <= 1 then
            yield 1
        else
            yield n
            if n % 2 = 0 then yield! f (n / 2)
            else yield! f (3 * n + 1) } )

Upvotes: 1

TheInnerLight
TheInnerLight

Reputation: 12184

The above answer is probably the easiest way of doing this but, purely for the sake of interest, there is a non-recursive solution:

type CollatzState = 
    |Continue of int
    |Stop

let collatz v =
    let unfolder =
        function
        |Stop -> None
        |Continue 1 -> Some (1, Stop)
        |Continue n when n % 2 = 0 -> Some(n, Continue <| n/2)
        |Continue n -> Some (n, Continue <| 3*n+1)
    Seq.unfold (unfolder) (Continue v)

We use Seq.unfold to generate numbers until the value 1 is reached, at which point we signal to stop.

The CollatzState type could equally well be another Option instead of a custom type but I think it's a little clearer what's happening this way.

Upvotes: 5

Lee
Lee

Reputation: 144136

You can use a sequence expression:

let rec collatzSeq n = seq {
    match n with
    | 1 -> yield 1
    | n when n % 2 = 0 ->
        yield n
        yield! collatzSeq (n / 2)
    | n ->
        yield n
        yield! collatzSeq (3 * n + 1)
}

Upvotes: 6

Related Questions