CODEWITHSUNDEEP
f#
user1325696
user1325696

Reputation: 625

F# Array.tryFindIndex start search from an index

I wonder if there's a cheap(performance wise) option to search an index of array element which meets certain criteria starting from an index?

Array.tryFindIndex method doesn't have an argument startIndex. I could do Array.skip(n) and then search there but it seems expensive to create an array just for search. How do I do this?

I looked List also doesn't have that argument. Do I have to use while ... do? Is there a nicer way?

Upvotes: 4

Views: 517

Answers (4)

Arkady
Arkady

Reputation: 1

For example, I'm searching for the LF character in an array of bytes starting from some startIndex. I have some class of different functions f, where I put function find10:

module Main =
  type f =
    static member find10(bytes:inref<byte[]>,i:int)=
      if i<bytes.Length && bytes[i]<>b10 then
        f.find10(&bytes,i+m1)
      else
        i

The constants m1 is 1 and b10 is byte 10. Now you can refer in your code like this:

let i=f.find10(&bytes,startIndex)

Upvotes: 0

dumetrulo
dumetrulo

Reputation: 1991

The base libraries try to provide functions for your convenience but they cannot possibly anticipate all use cases. Nothing wrong with writing your own if need be:

module Array =
    let tryFindIndexFrom i p (a : _ []) =
        let rec loop k =
            if k >= a.Length then None
            elif p a.[k] then Some k
            else loop (k + 1)
        if i < 0 then None else loop i

EDIT: p is the predicate testing the array elements. tryFindIndexFrom has the same signature as tryFindIndex but with the starting index added as first parameter.

EDIT 2: Added test for k < 0 for fool-proof usage.

EDIT 3: Moved test for k < 0 out of the loop as it needs to be checked only once.

Upvotes: 6

kaefer
kaefer

Reputation: 5751

Follow your instinct. Considering Array.skip but noting the obvious waste of allocating a second array, you can take it one step further and generalize to the lazily evaluated Seq.skip, compose it with the standard Seq.tryFindIndex function and add the offset, if applicable.

let tryFindIndexMin n p =
    Seq.skip n
    >> Seq.tryFindIndex p
    >> Option.map ((+) n)
// val tryFindIndexMin : n:int -> p:('a -> bool) -> (seq<'a> -> int option)

[ for i in 0..3 ->
    [|"a"; "b"; "a"; "b"|]
    |> tryFindIndexMin i ((=) "a") ]
// val it : int option list = [Some 0; Some 2; Some 2; null]

Upvotes: 2

TheQuickBrownFox
TheQuickBrownFox

Reputation: 10624

Here's a way to do it using a lazy sequence of array indexes:

let input = [| 'a' .. 'z' |]

seq { 4 .. input.Length - 1 }
|> Seq.tryFind (fun i -> input |> Array.tryItem i = Some 'x')

I'll leave it to you to generalise this into a helper function if you think that's necessary.

The nice thing about the current form is that it's quite flexible. You can change the maximum index easily, or search backwards, e.g. seq { input.Length - 1 .. -1 .. 4 }.

Upvotes: 2

Related Questions