在F#中实现递归列表理解的最常用方法

Question

简而言之，问题是:在F#中进行“递归列表理解”最常用的方法是什么？

更详细:据我所知(我是F#新手)，我们基本上有以下工具来“建立”列表: List.map和列表理解。由于它们或多或少做了相同的事情，它们通过“改变”给定列表的元素来生成一个列表(在理解的情况下，给定列表的形式是k..n)。

我想要做的是归纳地建立列表(在人们问到:除了好奇心之外没有其他原因)，也就是说，是否有任何内置的函数具有人们期望的行为，可以从一个名为"List.maplist“的函数中获取参数

函数f：'a List -> 'a和an n: int，

返回列表

长度为n的[...；f (f [])；f [] ]。

为了说明我的意思，我自己编写了这样一个函数(作为练习)

let rec recListComprehension f n =
    if n=0 then []
    else
        let oldList = recListComprehension f (n-1)
        f (oldList) :: oldList 

或者可读性稍差，但又是尾递归的：

let rec tailListComprehension f n list = 
    if n=0 then list
    else tailListComprehension f (n-1) ((f list)::list)

let trecListComprehension f n = tailListComprehension f n []

例如，包含前200个斐波那契数的列表可以通过以下方式生成

let fiboGen =
    function
    | a::b::tail -> a+b
    | _ -> 1UL

trecListComprehension (fiboGen) 200

总结这个问题:在F#中有没有一个内置函数，它的行为或多或少类似于"trecListComprehension“？如果没有，实现这种功能最常用的方式是什么？

PS:对不起，我有点罗嗦..

Answer 1

你基本上是在这个数字范围内使用fold。所以它可以写成：

let listComp f n = List.fold (fun xs _ -> f xs :: xs) [] [1 .. n]

这还有一个额外的好处，那就是可以优雅地处理n的负值。

Answer 2

在F#中做“递归列表理解”最常用的方法是什么？

这是风格的问题。您将更频繁地遇到高阶函数。对于某些情况，例如表达嵌套计算或实现懒惰，使用序列表达式似乎更自然。

为了说明，您的示例是在序列表达式中编写的：

let rec recListComprehension f n = seq { 
    if n > 0 then
        let oldList = recListComprehension f (n-1)
        yield f oldList
        yield! oldList }

recListComprehension fiboGen 200 |> Seq.toList

您拥有一个具有惰性和尾递归特性的可读性非常好的函数，这是使用Seq.unfold很难实现的。

类似地，笛卡尔乘积的嵌套计算对于使用序列表达式/列表理解更具可读性：

let cartesian xs ys = 
    [ for x in xs do
        for y in ys do
          yield (x, y) ]

而不是使用高阶函数：

let cartesian xs ys = 
    List.collect (fun x -> List.map (fun y -> (x, y)) ys) xs

我曾经问过differences between list comprehension and high-order functions，你可能会对它感兴趣。

Answer 3

你可以先做Seq.unfold，然后再做Seq.toList。

请参阅来自here的示例

let seq1 = Seq.unfold (fun state -> if (state > 20) then None else Some(state, state + 1)) 0

printfn "The sequence seq1 contains numbers from 0 to 20." 
for x in seq1 do printf "%d " x

let fib = Seq.unfold (fun state ->
    if (snd state > 1000) then None
    else Some(fst state + snd state, (snd state, fst state + snd state))) (1,1)

printfn "\nThe sequence fib contains Fibonacci numbers." 
for x in fib do printf "%d " x