無法弄清楚如何在F#中實作一個非常基本的任意樹

當這似乎與我的需求非常相關時，我發現了這個問題 - F# 中的樹表示

為了學習，我嘗試實作一個超級簡單的測驗，基本上和 Daniel 寫的一模一樣

 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- 的值。IE

  checkstuff (Leaf "z")

但我顯然沒有在上面使用它。無論傳遞的葉子的字串值如何，它始終回傳 true。這是有道理的 bc 唯一要檢查的樹是由單葉“z”組成的樹。好吧，也許我應該像這樣使用它

 t2 |> checkstuff (Leaf "z")

但這是錯誤的，因為它以及它的每一個細微變化都會產生型別不匹配錯誤

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

似乎我仍然沒有掌握這種語言的一些非常基本的方面，以及一般的遞回/折疊技術。我對該實作的最后一部分感到特別困惑

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

這里到底發生了什么？通過我的閱讀，我發現 (||) 是在函式呼叫樣式中使用的布林值或運算子，因此連續的“false”和 list.map 部分是該 OR '函式'（正確的？）。但是，作為折疊的累加器，它究竟是如何作業的呢？

我的兩個主要問題是

1. 我可以看到一個實際如何使用/呼叫上面顯示的 Tree 型別和 checkstuff 函式的功能示例（謝謝 Daniel），以查看樹中是否存在給定的字串值？
2. Can someone show how that implementation might be adapted to, say, concatenate all the string values in this tree? Or maybe find if any values match a pattern? Or really any example that involves a slight modification of the above would be so helpful

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

EDIT:

after experimenting some more with the answer below a lot of stuff finally "clicked" for me about F#. In retrospect, my "conceptual" understanding wasn't as poor as I thought, its just that my implementation was full of technical errors and syntax misuse. The common theme (besides trying to implement code I didn't fully understand :P ) was the misuse of parentheses. In many places I had annotations grouped together with parentheses when they should not have been. E.g

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

Should be

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

and definitely shouldn't be

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

In other places I had parameters for function calls grouped together when they shouldn't have been - or not properly grouped with the function call itself when they should have been - causing either errors or causing them to be interpreted as a single parameter and leading the compiler to thinking the next function it encountered was actually my final parameter.

And further some of my problems were also coming from me not using type annotations in contexts where the compiler really needs them. Certain types were being interpreted as generic when they should have been specific, so my custom types weren't matching as they should later in the program. This seems especially crucial if you are trying to use partial application on custom functions being used w/ the pipe operator.

所有這些不同的實體結合在一起，我的菜鳥意味著我收到了大量幾乎無法理解的編譯器錯誤，所有這些現在都變得更有意義了。

我會發布我的作業解決方案，但它與下面的答案幾乎相同，除了它使用的不是字串（字串 * 字串），所以我不確定它會增加多少價值。

TL;DR - 括號很重要

uj5u.com熱心網友回復：

恐怕您復制了一些不是很有用的代碼：checkstuff對于至少包含一個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＃ 树

上一篇：通過RegEx決議帶有不同引號的輸入字串

下一篇：為wiki制作一個更簡單的決議器函式