Tree Representation in F#

Question

I'm trying to implement a tree in F# using a list of tuples.
[a] where a = (string, [a])
Each node has a list of their children and leaf nodes would be (name, [])

I want to be able to recursively iterate through each level of the list like this.

    a
 b     e
c d   f g

They wont always be binary trees however.

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

let rec checkstuff tple =
    match tple with
    | (_, []) -> true
    | (node, children) ->
        List.fold ( || ) false (List.map checkstuff children)

I get:

Type mismatch. Expecting a
    ('a * 'b list) list
but given a
    'b list
The resulting type would be infinite when unifying ''a' and ''b * 'a list'

Is there a way I can do something like this or is there not support for a recursive list of tuples like this?

Answer 1

Try changing your data structure a bit:

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)

Answer 2

There are a couple ways to approach this, and Daniel's is nice. But here is another way (also using discriminant unions) to define a recursive data structure, this one being a bit closer to your own approach (though I think I may actually prefer Daniel's since the cases are more explicit):

type tree<'a> =
    | Node of 'a * list<tree<'a>>

let t3 = Node("a", [Node("b", [Node("c",[]); Node("d",[])]); Node("e", [Node("f",[]); Node("g",[])])])

let rec checkstuff tple =
    match tple with
    | Node(_, []) -> true
    | Node(node, children) ->
        List.fold ( || ) false (List.map checkstuff children)