无法弄清楚如何在 F# 中实现一个非常基本的任意树

Question

我很久以前就发现了这个问题，当时它似乎与我的需求非常相关 - Tree Representation in F#

为了学习，我试着实现了一个超级简单的测试，基本上完全按照丹尼尔写的那样

 type Tree =
     | Branch of string * Tree list
     | Leaf of string

 let t2 = Branch ("a", [Branch ("b", [Leaf "c"; Leaf "d"]); Branch ("e", [Leaf "f"; Leaf "g"])])

 let rec checkstuff tree =
      match tree with
      | Leaf _ -> true
      | Branch(node, children) -> List.fold (||) false (List.map checkstuff children)

在编译和运行时，我想我只是不确定如何实际使用它？在上面的示例中，无论成功输入的内容如何，我想出的成功调用该函数的唯一方法总是产生 -true- 的值。即

  checkstuff (Leaf "z")

但我显然没有在上面使用它。无论传递的叶的字符串值如何，它总是 returns true。这是有道理的，因为唯一要检查的树是由单叶“z”组成的树。好的，也许我应该像这样使用它

 t2 |> checkstuff (Leaf "z")

但这是错误的，因为它及其每一个细微的变化都会产生类型不匹配错误

  This expression was expected to have type    'Tree -> 'a'    but here has type    'bool'

看来我还没有掌握这门语言的一些非常基本的方面，以及一般的 recursion/fold 技术。我对该实现的最后一部分感到特别困惑

   List.fold (||) false (List.map checkstuff children)

这里到底发生了什么？通过阅读，我发现 (||) 是函数调用样式中使用的布尔值或运算符，因此连续的“false”和 list.map 部分是该 OR [= 的 2 个参数61=]（正确吗？）。但是，作为弃牌的累加器，它究竟是如何工作的呢？

我的两个主要问题是

我能看到一个功能示例，说明如何实际 use/call 上面显示的 Tree 类型和 checkstuff 函数（谢谢 Daniel），以查看给定的字符串值是否存在于树中？
有人可以展示该实现如何适应，比如说，连接这棵树中的所有字符串值吗？或者可能会发现是否有任何值与模式匹配？或者实际上任何涉及对上述内容稍作修改的示例都会非常有帮助

====================

编辑：

在对下面的答案进行了更多试验之后，我终于对 F# 有了很多了解。回想起来，我的“概念”理解并没有我想象的那么差，只是我的实现充满了技术错误和语法滥用。共同的主题（除了尝试实现我不完全理解的代码 :P ）是括号的误用。在许多地方，我将注释与括号放在一起，而这些注释本不应该放在一起。例如

  let funcles (x:string y:string) : string

应该是

  let funcles (x:string) (y:string) : string

绝对不应该

  let  funcles (x:string y:string :string)

在其他地方，我将函数调用的参数组合在一起，但它们不应该组合在一起——或者在它们应该组合在一起的时候没有正确地组合在一起——导致错误或导致它们被解释为单个参数并导致编译器认为它遇到的下一个函数实际上是我的最终参数。

此外，我的一些问题也来自于我没有在编译器真正需要它们的上下文中使用类型注释。某些类型在它们应该是特定的时候被解释为通用的，所以我的自定义类型不匹配，因为它们在程序的后面应该是匹配的。如果您尝试在使用管道运算符的自定义函数上使用部分应用程序，这似乎尤其重要。

所有这些不同的实例结合在一起，我的新手意味着我遇到了一大堆几乎无法理解的编译器错误，所有这些现在都变得更有意义了。

我会 post 我的工作解决方案，但它与下面的答案几乎相同，除了它使用的不是字符串 (string * string)，所以我不确定它会增加多少价值。

TL;DR - 括号很重要

Answer 1

恐怕您复制了一些不是很有用的代码：checkstuff 将 return 对任何至少包含一个 Leaf 的树成立。它只是简单地将其子结果递归或运算在一起，因此单个 true 值将保证最终结果也是 true.

要检查树中是否存在字符串，我会这样做：

let rec exists str = function
    | Leaf s -> s = str
    | Branch (s, children) ->
        if s = str then true
        else children |> List.exists (exists str)

exists "c" t2 |> printfn "%A"   // true
exists "x" t2 |> printfn "%A"   // false

为了连接树中的字符串，我会这样做：

let rec concat = function
    | Leaf s -> s
    | Branch (s, children) ->
        let childStr =
            children
                |> List.map concat
                |> String.concat ""
        $"{s}{childStr}"

concat t2 |> printfn "%s"   // abcdefg

无法弄清楚如何在 F# 中实现一个非常基本的任意树

Cannot figure out how to implement a very basic arbitrary tree in F#

tree

recursion

f#

parsing