根据以前的值创建序列

Question

我正在学习F#(第二天O :-))并且我想创建Collat​​z序列,其中每个值都是基于前一个计算的.我知道,在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;
}

或者如何在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"

但不要弄清楚序列解决方案......

Answer 1

你可以非常简洁地使用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)

Answer 2

您可以使用序列表达式:

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)
}

Answer 3

上面的答案可能是最简单的方法,但纯粹为了感兴趣,有一个非递归的解决方案:

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)

我们使用Seq.unfold生成数字直到1达到该值,此时我们发出信号停止.

该CollatzState类型同样可以是另一种Option,而不是一个自定义的类型,但我认为这是一个更清晰一点发生了什么这样.