Get elements between two elements in an F# collection

Question

I'd like to take a List or Array, and given two elements in the collection, get all elements between them. But I want to do this in a circular fashion, such that given a list [1;2;3;4;5;6] and if I ask for the elements that lie between 4 then 2, I get back [5;6;1]

Being used to imperative programming I can easily do this with loops, but I imagine there may be a nicer idiomatic approach to it in F#.

Edit

Here is an approach I came up with, having found the Array.indexed function

let elementsBetween (first:int) (second:int) (elements: array<'T>) =
    let diff = second - first
    elements 
    |> Array.indexed
    |> Array.filter (fun (index,element) -> if diff = 0 then false
                                            else if diff > 0 then index > first && index < second
                                            else if diff < 0 then index > first || index < second
                                            else false

This approach will only work with arrays obviously but this seems pretty good. I have a feeling I could clean it up by replacing the if/then/else with pattern matching but am not sure how to do that cleanly.

Answer 1

You should take a look at MSDN, Collections.Seq Module for example.

Let's try to be clever:

let elementsBetween a e1 e2 =
    let aa = a |> Seq.append a
    let i1 = aa |> Seq.findIndex (fun e -> e = e1)
    let i2 = aa |> Seq.skip i1 |> Seq.findIndex (fun e -> e = e2)
    aa |> Seq.skip(i1+1) |> Seq.take(i2-1)

Answer 2

I am not on my normal computer with an f# compiler, so I haven't tested it yet. It should look something like this

[Edit] Thank you @FoggyFinder for showing me https://dotnetfiddle.net/. I have now tested the code below with it.

[Edit] This should find the circular range in a single pass.

let x = [1;2;3;4;5]
let findCircRange l first second =
    let rec findUpTo (l':int list) f (s:int) : (int list * int list) = 
        match l' with 
        | i::tail -> 
            if i = s then tail, (f [])
            else findUpTo tail (fun acc -> f (i::acc)) s
        // In case we are passed an empty list.
        | _ -> [], (f [])
    let remainder, upToStart = findUpTo l id first
    // concatenate the list after start with the list before start. 
    let newBuffer = remainder@upToStart
    snd <| findUpTo newBuffer id second

let values = findCircRange x 4 2
printf "%A" values

findUpTo takes a list (l'), a function for creating a remainder list (f) and a value to look for (s). We recurse through it (tail recursion) to find the list up to the given value and the list after the given value. Wrap the buffer around by appending the end to the remainder. Pass it to the findUpTo again to find up to the end. Return the buffer up to the end.

We pass a function for accumulating found items. This technique allows us to append to the end of the list as the function calls unwind.

Of course, there is no error checking here. We are assuming that start and end do actually exist. That will be left to an exercise for the reader.

Answer 3

Here is a variation using your idea of diff with list and list slicing <some list.[x .. y]

let between (first : int) (second : int) (l : 'a list) : 'a list =
    if first < 0 then
        failwith "first cannot be less than zero"
    if second < 0 then
        failwith "second cannot be less than zero"
    if first > (l.Length * 2) then
        failwith "first cannot be greater than length of list times 2"
    if second > (l.Length * 2) then
        failwith "second cannot be greater than length of list times 2"

    let diff = second - first
    match diff with
    | 0 -> []
    | _ when diff > 0 && (abs diff) < l.Length -> l.[(first + 1) .. (second - 1)]
    | _ when diff > 0 -> (l@l).[(first + 1) .. (second - 1)]
    | _ when diff < 0 && (abs diff) < l.Length -> l.[(second + 1)  .. (second + first - 1)]
    | _ when diff < 0 -> (l@l).[(second + 1)  .. (second + first - 1)]