Base case not getting picked up in my F# function

February 20, 2022

This function is supposed to just return the index of a list. That part works. However when a element is not in a list it must return -1.

For some reason it does not return -1.

let rec search f list =
    match list with
    | head::tail ->
           if f head then 0 
           else 1 + search f tail
    | [] -> -1



printfn "%A" (search (fun x -> x = 5) [ 5; 4; 3; 2 ])
//>> return index 0 for #5

printfn "%A" (search (fun x -> x = 6) [ 5; 4; 3; 2 ])
//>> should return -1 but it returns 3 which is the len of the list not -1

EDIT: Can not use nested functions.

>Solution :

You could use e.g.

let search f list =
  let rec where at list =
    match list with
    | [] -> -1
    | head::tail ->
        if f head then at
        else where (at + 1) tail
  where 0 list

which has the benefit of being tail-recursive. Regarding your comment:

let rec search f list =
  match list with
  | [] -> -1
  | head::tail ->
      if f head then 0 else
        match search f tail with
        | -1 -> -1
        | i -> i + 1