CODEWITHSUNDEEP
f#treefold
E. Peracchia
E. Peracchia

Reputation: 113

Re-create a "tree contains element" with foldback. I don't understand why it's working

I was trying to recreate with a Foldback a function that given a tree and an element x, it will output true if the element is inside the tree, false instead.

This is my tree:

type 'a binTree =
  | Null                                     // empty tree
  | Node of 'a  * 'a binTree * 'a binTree

This is my code without the foldback

let rec containsTreeBis bTree y =
match bTree with 
    | Null -> false
    | Node(x,left,right) -> 
        match x=y with 
            | true -> true 
            | _ -> containsTreeBis left y || containsTreeBis right y

And this is my foldTree function which applies the fold to a tree:

let rec foldTree f e tree = 
match tree with
  | Null -> e
  | Node (x, left, right) ->
    f x ( foldTree f e left )  ( foldTree f e right )

They both are working pretty good.

Now to the problem.

I tried to use the foldTree to do the same thing. I was really convinced and sure that this was the right code

 let containsTreeF bTree pred = 
    foldTree ( fun y vl vr -> pred y || vl || vr ) true bTree

but doing some checks with FsCheck, it turns out the result is Falsiable.

I randomly changed the code to this:

 let containsTreeF bTree pred = 
    foldTree ( fun y vl vr -> pred y || vl || vr ) false bTree

Changed the true at the end with false.

Did the FsCheck. It works.

How? I'm not getting it.

Upvotes: 0

Views: 83

Answers (1)

Tomas Petricek
Tomas Petricek

Reputation: 243051

Your fold function is implemented correctly and so the question is about how to use the fold function to check whether a tree (or anything with a fold operation) contains a specified element.

To do this, you need to use false as the initial value and logical or as the operation, i.e:

let contains x tree = 
  foldTree (fun y vl vr -> x = y || vl || vr) false tree

This will return false for an empty tree. If either branch contains the element then true || false will be true, but if none of the brnaches contain it then false || false will result in false.

How come your FsCheck tests did not catch this when you had true as the initial value? With that initial value, your function will always return true, so you would catch this with a test that looks for an element that is not contained in a tree.

A unit test for that would be:

let t = Node(1, Node(2, Null, Null), Null)
contains 7 t

With FsCheck, you could generate tree with values from some randomly generated set and then check that it contains an item that is not in this set.

Upvotes: 1

Related Questions