CODEWITHSUNDEEP
recursiontreef#functional-programming
user3711518
user3711518

Reputation: 253

F# searching in trees F#

Find an 'item/object/type' in a recursive tree type, the tree type is UNSORTED, thus binary search operation is not going to succeed.

Type Tree = T of (Name*Children)
And Children = Tree list
//findTree :Tree*Name -> Tree

My code(which doesn't work)

let rec findTree t n = List.find(fun (T(nameTree,childTree)) -> n=nameTree ) t

I've tried using recursion and auxFunctions, but it ends up being very messy with no success.

Upvotes: 0

Views: 559

Answers (1)

Patryk Ćwiek
Patryk Ćwiek

Reputation: 14318

Your base type is essentially this (cleaned up missing types):

type Tree = 
    | Tree of (string * Tree list)

Now the tree is unsorted, so the best you can do is a linear search, recursively going down the child nodes until a match is found. In the following case, the search goes depth-first:

[<CompilationRepresentationAttribute(CompilationRepresentationFlags.ModuleSuffix)>]
module Tree = 
    let find p tree = 
        let rec findInner t =
            match t with
            | Tree(n, _) when p(n) -> Some(t)
            | Tree(_, children) -> children |> Seq.choose (findInner) 
                                            |> Seq.tryFind (fun _ -> true)
            | Tree(_, []) -> None
        findInner tree

You can use List.choose and List.tryFind if you want, I used Seq so it would stop early on tryFind. Also, this version has a predicate match on name. If you always want to use equality, you can add the name as parameter and swap p for name and when p(n) to when n = name.

Now, a little test:

let tree = Tree("A", 
                [Tree("B", 
                    [Tree("C",[]); 
                     Tree("D", 
                        [Tree("E",[])])
                    ]); 
                Tree("F",[])
                ])

tree |> Tree.find (fun n -> n = "B") |> printfn "%A"
tree |> Tree.find (fun n -> n = "D") |> printfn "%A"
tree |> Tree.find (fun n -> n = "E") |> printfn "%A"
tree |> Tree.find (fun n -> n = "TEST") |> printfn "%A"
tree |> Tree.find (fun n -> n = "F") |> printfn "%A"

Which prints, respectively:

Some (Tree ("B", [Tree ("C", []); Tree ("D", [Tree ("E", [])])]))
Some (Tree ("D", [Tree ("E", [])]))
Some (Tree ("E", []))
<null>
Some (Tree ("F", []))

Upvotes: 4

Related Questions