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，然后在树上进行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的近似开始(list提供结构模式匹配，而seq不提供……我希望从来没有人使用过这种实现(：
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的fold(
旁白：在完成任务并写出这个问题后，我现在认为将输入函数放入树结构中可能一点也不浪费，我应该更好地利用它。也就是说，我仍然太好奇了，不能放弃这个任务！
使用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返回一个列表——您可以在最后一行之前插入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，而是不断地分配越来越多的内存，所以我想它是有效的！