functional-programming - 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 }

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

方案一

将ls函数转化为玫瑰树，然后在树上做一个预排序的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 提供结构模式匹配，而 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 的折叠)？

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

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 返回一个列表 - 您可以在最后一行之前插入 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，而是不断分配越来越多的内存，所以我想它可行!