CODEWITHSUNDEEP
f#
cm007
cm007

Reputation: 1392

How to find index of last element in list matching predicate?

I would like to get the last index of an element in a list matching a predicate. I know I can use the following code for an array, but I am wondering if there is a way to do this for a list (without converting to an array and using the below function):

let tryFindLastIndex f (arr: 'a []) =
    let rec loop n (arr: 'a []) =
        match n with
        | -1 -> None
        | n ->
            if f arr.[n] then Some n
            else loop (n-1) arr
    loop (arr.Length - 1) arr

Upvotes: 2

Views: 1172

Answers (2)

Gene Belitski
Gene Belitski

Reputation: 10350

I'd approach this task with idiomatic use of library functions and combinators:

let tryFindLastIndex f ls =
    match ls |> (List.rev >> List.tryFindIndex f) with
    | None -> None
    | Some n -> Some (ls.Length - n - 1)

EDIT: for those who are over concerned with performance, the same can be achieved by single list traverse with the same clarity of intent still using library functions and combinators:

let tryFindLastIndex f ls =
    match (ls |> List.fold (fun (i,r) l -> if f l then (i+1,i::r) else (i+1,r)) (0,[]) |> snd) with
    | [] -> None
    | x -> Some (x.Head)

Upvotes: 4

MarcinJuraszek
MarcinJuraszek

Reputation: 125620

list in F# is a linked list you can't easily iterate in last->first direction. Because of that you have to iterate from the beginning and keep the track of both current index and index of last element that matches the predicate.

You still use local recursive function to do that.

let tryFindLastIndex f source =
    let rec loop index lastFoundIndex source =
        let newIndex = index+1
        match source with
        | [] -> lastFoundIndex
        | head :: tail ->
            if f head then loop newIndex (Some index) tail
            else loop newIndex lastFoundIndex tail
    loop 0 None source

Upvotes: 3

Related Questions