是否可以用List.unfold来列出N的所有因素？

Question

我正在尝试使用F#进行函数式编程。我现在坚持纯粹的数学问题。

我目前的问题很简单:编写一个接受整数N并输出N的所有因子的list的函数。

由于sequences和C# IEnumerables之间的相似之处，由yield return组成，我得到了以下解决方案：

let seqFactorsOf n =
    seq { for i in 2 .. (n / 2) do if n % i = 0 then yield i }

不过，我不认为lists是以这种方式生成的，所以我转向List.unfold

let listFactorsOf n =
    2 |> List.unfold (fun state ->
        if state <= n / 2 then
            if state % 2 = 0 then
                Some (state, state + 1)
            else
                //need something here to appease the compiler. But what?
        else
            None)

我的另一次尝试使用了匹配的概念，我对此几乎完全不熟悉：

let listFactorsOf_2 n =
    2 |> List.unfold(fun state ->
        match state with
        | x when x > n / 2 -> None
        | x when n % x = 0 -> Some(x, x + 1)
        //I need a match for the general case or I get a runtime error
        )

有没有一种方法可以使用list创建这样的List.unfold？请注意，我是个初学者(我3天前就开始使用F#了)，文档对新手不是很好，所以如果你想尽可能地说教的话，我会非常感激的。

Answer 1

First -是的，当然可以使用for..in语法生成列表(顺便说一句，它被称为“列表理解”)。把整件事放在方括号里而不是seq { }

let seqFactorsOf n =
    [ for i in 2 .. (n / 2) do if n % i = 0 then yield i ]

对于unfold，每个迭代都需要生成结果列表的一个元素(通过返回Some)，或者通过返回None发出迭代结束的信号。您无法从unfold的主体返回指示“跳过”元素的任何内容。

相反，您需要做的是自己“跳过”不需要的元素，并且只返回下一个除数(或None)。

这样做的一种方法是使用助手函数：

let rec nextDivisor n i =
    if n % i = 0 then Some i
    else if i >= n/2 then None
    else nextDivisor n (i+1)

让我们来测试一下：

nextDivisor 16 3
> Some 4

nextDivisor 16 5
> Some 8

nextDivisor 16 10
> None

现在我们可以在unfold的主体中使用它了

let listFactorsOf n =
    2 |> List.unfold (fun state ->
        match nextDivisor n state with
        | Some d -> Some (d, d + 1)
        | None -> None
    )

作为一个好处，构造match x with Some a -> f a | None -> None是一个众所周知和广泛使用的概念，通常被称为“地图”。在这种特殊情况下-是Option.map。因此，可以这样改写上面的内容：

let listFactorsOf n =
    2 |> List.unfold (fun state ->
        nextDivisor n state 
        |> Option.map (fun d -> d, d+1)
    )