Filter an array or list by consecutive pairs based on a matching rule

Question

This is probably trivial, and I do have a solution but I'm not happy with it. Somehow, (much) simpler forms don't seem to work and it gets messy around the corner cases (either first, or last matching pairs in a row).

To keep it simple, let's define the matching rule as any two or more numbers that have a difference of two. Example:

> filterTwins [1; 2; 4; 6; 8; 10; 15; 17]
val it : int list = [2; 4; 6; 8; 10; 15; 17]

The code I currently use is this, which just feels sloppy and overweight:

let filterTwins list =
    let func item acc =
        let prevItem, resultList = acc
        match prevItem, resultList with
        | 0, [] 
            -> item, []
        | var, [] when var - 2 = item
            -> item, item::var::resultList
        | var, hd::tl when var - 2 = item && hd <> var
            -> item, item::var::resultList
        | var, _ when var - 2 = item
            -> item, item::resultList
        | _ 
            -> item, resultList

    List.foldBack func list (0, [])
    |> snd

I intended my own original exercise to experiment with List.foldBack, large lists and parallel programming (which went well) but ended up messing with the "easy" part...

Guide through the answers

• Daniel's last, 113 characters*, easy to follow, slow
• Kvb's 2nd, 106 characters* (if I include the function), easy, but return value requires work
• Stephen's 2nd, 397 characters*, long winded and comparably complex, but fastest
• Abel's, 155 characters*, based on Daniel's, allows duplicates (this wasn't a necessity, btw) and is relatively fast.

There were more answers, but the above were the most distinct, I believe. Hope I didn't hurt anybody's feelings by accepting Daniel's answer as solution: each and every one solution deserves to be the selected answer(!).

* counting done with function names as one character

Answer 1

Would this do what you want?

let filterTwins l = 
    let rec filter l acc flag =
        match l with
        | [] -> List.rev acc
        | a :: b :: rest when b - 2 = a -> 
            filter (b::rest) (if flag then b::acc else b::a::acc) true
        | _ :: t -> filter t acc false
    filter l [] false

This is terribly inefficient, but here's another approach using more built-in functions:

let filterTwinsSimple l =
    l 
    |> Seq.pairwise 
    |> Seq.filter (fun (a, b) -> b - 2 = a)
    |> Seq.collect (fun (a, b) -> [a; b])
    |> Seq.distinct
    |> Seq.toList

Maybe slightly better:

let filterTwinsSimple l =
    seq { 
        for (a, b) in Seq.pairwise l do
            if b - 2 = a then 
                yield a
                yield b 
    }
    |> Seq.distinct
    |> Seq.toList