Immuitable recursive linear search of an array of string
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 &gt;= l -&gt; -1
                | _ -&gt; 
                    match array.[index] with 
                    | x when x = target -&gt; index
                    | y -&gt; 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 &gt;= l -&gt; -1
                | _ -&gt; 
                    match array.[index] with 
                    | x when x = target -&gt; index
                    | y -&gt; 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 &gt;= 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 &gt;= array.Length then
              None
            elif target = array.[index] then
              Some index
            else
              search (index + 1)
    search 0


But that's up to you.

Exercise


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

linearFind (array : 'a[]) (predicate: a' -&gt; bool) = …


If linearFind returns Some index, then predicate array.[index] should be true.
Express linearSearch in terms of linearFind.