I found this question from way back when that seemed quite relevant to my needs - Tree Representation in F#

for the sake of learning I tried implementing a super simple test basically exactly as Daniel had written

 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) 

And while this compiles and runs, I guess I'm just not sure how to actually use it? With the above example, the only way I could figure out to successfully call the function always yields a value of -true- regardless of the content of the successful input. i.e

  checkstuff (Leaf "z")

But I'm obviously not using it right above. It always returns true regardless of the string value of the leaf passed. That makes sense bc the only tree its been given to check is a tree consisting of the single leaf "z". Ok so maybe I'm supposed to use it like this

 t2 |> checkstuff (Leaf "z")

But that's wrong because it, and every slight variation of it, yields a type mismatch error

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

It seems like I am still not grasping some very fundamental aspects of this language, and recursion/fold techniques in general. I am particularly confounded by the last chunk of that implementation

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

What exactly is going on here? Through my reading I've found that the (||) is the boolean or operator being used in the style of a function call, so the successive "false" and list.map parts are the 2 parameters of that OR 'function' (correct?). But how exactly does that work as the accumulator for the fold?

My two main questions are

1. Can I see a functioning example of how one would actually use/call the Tree type and checkstuff function shown above (thank you Daniel), to see if a given string value exists in the tree?
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.

All of these different instances combined and my noob-ness meant I was getting a barrage of virtually incomprehensible compiler errors, all of which now make a lot more sense.

I would post my working solution but its nearly identical to the answer below, except instead of a string it uses (string * string), so i'm not sure it would add much value.

TL;DR - PARENTHESES ARE IMPORTANT

CodePudding user response：

I'm afraid you've copied some code that isn't very useful: checkstuff will return true for any tree that contains at least one Leaf. It simply recursively OR's together its child results, so a single true value will guarantee that the final result is also true.

To check if a string exists in a tree, I would do this:

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

To concatenate the strings in a tree, I would do this:

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