Immuitable recursive linear search of an array of string

Question

I am new to F#. Is the following code, which represents about three hours of work, a canonical way to achieve its goals. If not, how can it be improved?

For instance, can we provide a default value of zero for the index parameter? Also, how do we handle a search for a term that does not exist? Could we use something similar to tail::head instead of matching against array.[index]? It looks more verbose that it needs to be.

open System

let rec linearSearch (array: string[]) (target: string) (index: int) = 
    match array.Length with 
    | l when index >= l -> -1
    | _ -> 
        match array.[index] with 
        | x when x = target -> index
        | y -> linearSearch array target (index + 1)

[<EntryPoint>]
let main argv =
    let names = [|
        "erdnase"
        "vernon"
        "le paul"
        "scarne"
        "ireland"
    |]
    linearSearch names "le paul" 0 |> printfn "The target is at index: %A" 
    linearSearch names "luttin" 0 |> printfn "The target is at index: %A" 
    0 

The goals for writing the code were:

1. Use an array instead of a list, because I would like to understand F# arrays.
2. Implement a linear search, because it is a simple algorithm.
3. Write in canonical F#, because canonical code is more maintainable.

Answer 1

The additional argument index is error prone. For example, a user might provide -1 and you end up with array.[-1]. So let us get rid of that first:

let linearSearch (array: string[]) (target: string) = 
    let rec search index = 
            match array.Length with 
                | l when index >= l -> -1
                | _ -> 
                    match array.[index] with 
                    | x when x = target -> index
                    | y -> search (index + 1)
    search 0

Now the recursive call is hidden in search, and also the index cannot get negative or otherwise mangled by a user. Next, we can make your linearSearch more general:

let linearSearch (array: 'a[]) (target: 'a) = 
    let rec search index = 
            match array.Length with 
                | l when index >= l -> -1
                | _ -> 
                    match array.[index] with 
                    | x when x = target -> index
                    | y -> search (index + 1)
    search 0

After all it should work for anything we can compare with =. Talking about comparing something, your pattern matches aren't really matching anything. You're just checking whether a condition has been met. Use usual structures instead:

let linearSearch (array: 'a[]) (target: 'a) = 
    let rec search index = 
            if index >= array.Length then
              -1
            elif target = array.[index] then
              index
            else
              search (index + 1)
    search 0

And last but not least, I would use the same promises as the usual C#/F# functions: either throw an exception when the value has not been found, or return an Option. That way, if we got an int, it's valid, so we don't have to check for an invalid position. I've choosed option:

let linearSearch (array: 'a[]) (target: 'a) = 
    let rec search index = 
            if index >= array.Length then
              None
            elif target = array.[index] then
              Some index
            else
              search (index + 1)
    search 0

But that's up to you.

Exercise

1. Write a function linearFind that uses a function to find the correct index:

   linearFind (array : 'a[]) (predicate: a' -> bool) = …
   

   If linearFind returns Some index, then predicate array.[index] should be true.

2. Express linearSearch in terms of linearFind.

Answer 2

When your match expression has many when guards and no actual patterns, it's a sign that you're abusing it. Use if/else instead:

if array.Length <= index then 
  -1
elif array.[index] = x then 
  index
else
  linearSearch array target (index + 1)