是列表推导 for 和 yield! F# 中的尾递归？

Question

这是我写的，为了便于参考，我会在这里重复一遍：

/// Take a list of lists, go left-first, and return each combination,
/// then apply a function to the resulting sublists, each length of main list
let rec nestedApply f acc inp =
    match inp with
    | [] -> f acc
    | head::tail -> 
        [
            for x in head do
                yield! nestedApply f (x::acc) tail
        ]

这让我想知道在这种情况下使用 yield! 或通常使用列表理解是否是尾递归的。我实际上认为不是，这使得上述函数将创建一个等于主列表大小的堆栈深度。

如果不是，我如何以尾递归方式编写相同的代码？我已经尝试过 List.collect（一个推出的想法在提到的问题中），但我没有完全到达那里。

Answer 1

不，这不是尾递归，实际上会炸毁堆栈：

let lists = 
    [1 .. 10000]
    |> List.map (fun i -> List.replicate 100 i)

nestedApply id [] lists

您可以通过以连续传递方式重写它来使 nestedApply 尾递归，但它不只是一个 n 元笛卡尔积后跟一个映射吗？

Answer 2

为了简化事情，我将把列表的乘法与函数的映射分开。所以 nestedApply 看起来像这样：

let nestedApply f lsts = mult lsts |> List.collect f

其中 mult 执行列表的乘法运算，return 执行所有组合。

我通常发现做尾递归最好先从简单递归开始：

let rec mult lsts =
    match lsts with
    | [ ]       ->  [[]]
    | h :: rest ->  let acc = mult rest
                    h |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) )

所以这个版本的 mult 完成了这项工作，但它不使用尾递归。它确实用作创建尾递归版本的模板，我可以检查两者 return 是否具有相同的值：

let mult lsts =
    let rec multT lsts acc =
        match lsts with
        | h :: rest -> h 
                       |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) ) 
                       |> multT rest
        | [ ]       -> acc
    multT (List.rev lsts) [[]]

尾递归版本multT 使用内部累加器参数。为了隐藏它，我将递归部分嵌套在函数 mult 中。我还颠倒了列表，因为这个版本向后工作。

很多时候当你有一个尾递归函数时，你可以使用fold函数来消除递归：

let mult lsts  = 
    List.rev lsts 
    |> List.fold  (fun acc h -> 
           h 
           |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) ) 
         ) [[]]

或foldBack:

let mult lsts =
    List.foldBack (fun h acc -> 
        h 
        |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) ) 
      ) lsts [[]]

注意相似之处。

这是fiddle中的解决方案：

https://dotnetfiddle.net/sQOI7q

是列表推导 for 和 yield! F# 中的尾递归？

Are list comprehensions with for and yield! tail-recursive in F#?

list

f#

yield

tail-recursion

computation-expression