CODEWITHSUNDEEP
f#
Alex
Alex

Reputation: 397

F# Weird pattern matching result

I'm writing a binary search implementation. The problem I have is with a pattern matching block.

This code using pattern matching returns weird results. The first match block does not return what I expect. It warns me that (_,_) is never reached.

let binSearch (item:double) (arr:list<double>) =
    let rec binSearchRec first last =
        if first > last then
            let lastIndex = arr.Length-1
            let len = arr.Length
            match (first, last) with
            | (0, -1) -> System.String.Format("ITEM SMALLER THAN {0}", arr.[0])
            | (len, lastIndex) -> System.String.Format("ITEM BIGGER THAN {0}", arr.[lastIndex])
            | (_,_) -> System.String.Format("IN BETWEEN {0} AND {1}", arr.[last], arr.[first])
        else
            let mid = (first+last)/2
            match item.CompareTo(arr.[mid]) with
            | -1 -> binSearchRec first (mid-1)
            | 0 -> "CONTAINS"
            | 1 -> binSearchRec (mid+1) last
    binSearchRec 0 (arr.Length-1)

Replacing that first match (first, last) call with this if-else alternative works well:

if first = 0 && last = -1 then
    System.String.Format("ITEM SMALLER THAN {0}", arr.[0])
else if first = len && last = lastIndex then
    System.String.Format("ITEM BIGGER THAN {0}", arr.[lastIndex])
else
    System.String.Format("IN BETWEEN {0} AND {1}", arr.[last], arr.[first])

I don't understand how that match call is different from this if-else call and why this works well but the pattern matching block does not.

A weird result is that printing len in the (len, lastIndex) match returns wrong numbers inside the match. For an array of length three a print of len before the match statement will show 3 whereas a print inside the match will show 1.

Upvotes: 3

Views: 404

Answers (1)

Bartek Kobyłecki
Bartek Kobyłecki

Reputation: 2395

One of your branch in match expression is creating new bindings to existing symbols

| (len, lastIndex) -> ...

so this branch matches with every other case.

If you what to match against existing values in match expression you can use when clase for that:

| (a, b) when a = len && b = lastIndex -> ...

Another option would be declaring len and lastIndex as literals to use them in pattern matching but it seems not natural in your case.

[<Literal>]
let len = arr.Length

Upvotes: 8

Related Questions