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.

• BenKoshy: what is this code meant to do?
• Zeta: @BKSpurgeon return the index of an element if it exists, -1 otherwise.

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.

• Shaun Luttin: Wrapping the recursive call in a non-recursive call reminds me of the facade pattern from object-oriented programming.

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)

• Shaun Luttin: Thank you. Your answer reminds me of this: "The moral of the tale is: if you find yourself using if-then-else or matching on booleans, consider refactoring your code." fsharpforfunandprofit.com/posts/control-flow-expressions