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

Question

tldr；转到我的问题

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

假设我有以下函数（以便为具有相同结构属性且类型为 '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，然后在树上做一个pre-order 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 不t...我希望没有人使用过这个实现）：

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 的情况？）；和
没有明确的自递归（例如使用 accumulator/cps 的折叠）？

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

Answer 1

您可以使用 F# 序列表达式和 yield 和 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 到 return 一个列表 - 您可以在最后一行之前插入 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

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

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

F# - Traverse a tree defined not as a structure, but as a function: ls: 'a -> 'a seq

functional-programming

f#

depth-first-search

tail-recursion

preorder

解决方案 1

解决方案 2

我的问题