F# - 遍历不是定义为结构而是定义为函数的树： ls: 'a -> 'a seq

Question

太棒了；转到我的问题

我相信这里提出的问题一定不是什么新问题，但我没有找到任何直接对应的讨论。

假设我有以下函数（为了提供具有相同结构属性的实际函数的确定性替代，类型为'a -> 'a seq）：

// I'm a function that looks suspiciously like a tree
let lsExample x =
    match x with
    | 0 -> seq { 1; 6; 7 }
    | 1 -> seq { 2; 3 }
    | 3 -> seq { 4; 5 }
    | 7 -> seq { 8; 9 }
    | _ -> Seq.empty

现在，我希望拥有以下内容：

let lsAll: ('a -> 'a seq) -> 'a -> 'a seq

这样

lsAll lsExample 0

评估为

seq { 0 .. 9 }

我找到了一个冗长的解决方案，以及一个简单但仍然不理想的类似问题的解决方案。

解决方案1

将函数转换ls为Rose Tree，然后对树做预序dfs，如下：

open FSharpx.Collections
module L = LazyList
module R = Experimental.RoseTree

let rec asRoseTree (ls: 'a -> seq<'a>) (item: 'a) =
    let children = ls item
    if (Seq.isEmpty children) then
        R.singleton item
    else
        children
        |> Seq.map (asRoseTree ls)
        |> L.ofSeq
        |> R.create item

let lsAll ls =
    asRoseTree ls >> R.dfsPre

解决方案2

完成工作后，我想要一个更优雅的解决方案，因此从使用这种近似开始'a -> 'a list（lists 提供结构模式匹配，而seqs 不...我希望没有人使用此实现）：

let rec lsAll' (ls: 'a -> 'a list) (xs: 'a list) =
    match xs with
    | [] -> []
    | [x] -> lsAll' ls (ls x) |> List.append [x]
    | x :: tail -> lsAll' ls tail |> List.append (lsAll' ls [x])

let lsAll ls x = lsAll' ls [x]

然后，即使没有切换回 seq 带来的额外不便，我还是在尝试使尾递归时陷入困境。

我的问题

我们如何实施lsAll：

• 无需构建中间的、显式的树结构；
• 具有所需的类型（seq，而不是列表）；
• 使用尾递归（CPS 的一个例子？）；和
• 没有显式的自递归（例如使用带有累加器/cps的折叠）？

旁白：完成工作并写下这个问题后，我现在认为将输入函数放入树结构可能根本不是浪费，我应该更好地利用它。也就是说，我仍然很好奇，不能放弃这个任务！

Answer 1

yield您可以使用 F# 序列表达式以及and结构很好地做到这一点yield!：

let rec lsAll ls x = seq {
  yield x
  for c in ls x do
    yield! lsAll ls c }

lsAll lsExample 0

序列表达式seq { .. }是生成序列的代码块。在此内部，您可以将yield单个元素添加到序列中，也yield!可以添加其他序列的所有元素。在这里，您可以执行此操作以包含递归调用生成的所有值。

您也可以将其与解决方案 2 中的方法结合起来：

let rec lsAll ls xs = seq {
  match xs with 
  | [] -> ()
  | x::xs -> 
      yield x
      yield! lsAll ls (ls x)
      yield! lsAll ls xs }

这需要lsAll返回一个列表 - 您可以List.ofSeq在最后一行之前插入，但我认为最好将其留给用户。但是，您现在可以使用 CPS 将其转换为尾递归版本，其中延续是“当前值完成后要生成的值序列”：

let rec lsAll ls xs cont = seq {
  match xs with 
  | [] -> yield! cont
  | x::xs -> 
      yield x
      yield! lsAll ls (ls x) (lsAll ls xs cont) }

lsAll (lsExample >> List.ofSeq) [0] Seq.empty

如果我给它一个无限树，它实际上并不是 StackOverflow，而是不断分配越来越多的内存，所以我想它是有效的！