Does F# have loop exit statement?

Question

I know recursive function is a powerful technique in F#. My question is: Is there an exit statement, which can jump out recursive functions, just like imperative languages. For example, Insert a node to a binary tree.

type Tree<'a> when 'a :> IComparable<'a> =
           | Nil
           | Leaf of 'a
           | Node of Tree<'a> * 'a * Tree<'a>

let tt2 = Node(
              Node(Leaf "D", "B",Node(Leaf "G", "E", Leaf "H" )),
              "A",
              Node(Nil, "C", Node(Nil, "F", Leaf "I")))

let rec contains (x : #IComparable<'a>) = function
    | Nil -> false
    | Leaf y -> if x.CompareTo(y) = 0 then true else false
    | Node(l, y, r) -> 
         match l, y, r with
             | l, y, Nil -> if x.CompareTo(y) = 0 then true else contains x  l
             | Nil,y, r -> if x.CompareTo(y) = 0 then true else contains x r 
             | _ -> if x.CompareTo(y) = 0 then true
                    else contains x r |>ignore
                         contains x l

let xx = contains "C"  tt2  //It is wrong answer.

Answer 1

Is there an exit statement, which can jump out recursive functions, just like imperative languages.

No. The very reason is that you can encode imperative break/return by recursive functions and pattern matching. If you would like to break, just return a value, otherwise invoke another recursive call.

This question is more appropriate to ask for high-order functions. When you need early exit on high-order functions, writing custom recursive function is the way to go. If you are interested in imperative constructs in F#, take a look at the excellent series by @Tomas.

Your function will exit at some branch when the condition is determined. The only problem is that you should not discard contain x r in the second to last line.

You can remove superfluous if/else for clarity

let rec contains (x : #IComparable<'a>) = function
    | Nil -> false
    | Leaf y -> x.CompareTo(y) = 0
    | Node(l, y, r) -> 
         match l, y, r with
         | l, y, Nil -> x.CompareTo(y) = 0 || contains x l
         | Nil,y, r -> x.CompareTo(y) = 0 || contains x r 
         | _ -> x.CompareTo(y) = 0 || contains x l || contains x r