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

Answer 2

How about this?

let filterPairs f =
  let rec filter keepHead = function
  | x::(y::_ as xs) when f x y -> x::(filter true xs)
  | x::xs -> 
      let rest = filter false xs
      if keepHead then x::rest else rest
  | _ -> []
  filter false

let test = filterPairs (fun x y -> y - x = 2) [1; 2; 4; 6; 8; 10; 15; 17]

Or if all of your list's items are unique, you could do this:

let rec filterPairs f s =
  s
  |> Seq.windowed 2
  |> Seq.filter (fun [|a;b|] -> f a b)
  |> Seq.concat
  |> Seq.distinct

let test = filterPairs (fun x y -> y - x = 2) [1; 2; 4; 6; 8; 10; 15; 17]

EDIT

Or here's another alternative which I find elegant. First define a function for breaking a list into a list of groups of consecutive items satisfying a predicate:

let rec groupConsec f = function
| [] -> []
| x::(y::_ as xs) when f x y -> 
    let (gp::gps) = groupConsec f xs 
    (x::gp)::gps
| x::xs -> [x]::(groupConsec f xs)

Then, build your function by collecting all results back together, discarding any singletons:

let filterPairs f =
  groupConsec f
  >> List.collect (function | [_] -> [] | l -> l)

let test = filterPairs (fun x y -> y - x = 2) [1; 2; 4; 6; 8; 10; 15; 17]

Answer 3

The following solution is in the spirit of your own, but I use a discriminate union to encapsulate aspects of the algorithm and reign in the madness a bit:

type status =
    | Keep of int
    | Skip of int
    | Tail

let filterTwins xl = 
    (Tail, [])
    |> List.foldBack
        (fun cur (prev, acc) ->
            match prev with
            | Skip(prev) when prev - cur = 2 -> (Keep(cur), cur::prev::acc)
            | Keep(prev) when prev - cur = 2 -> (Keep(cur), cur::acc)
            | _ -> (Skip(cur), acc))
        xl
    |> snd

Answer 4

Here's another solution which uses a similar discriminate union strategy as my other answer but it works on sequences lazily so you can watch those twin (primes?) roll in as they come:

type status =
    | KeepTwo of int * int
    | KeepOne of int
    | SkipOne of int
    | Head

let filterTwins xl = 
    let xl' =
        Seq.scan
            (fun prev cur ->
                match prev with
                | KeepTwo(_,prev) | KeepOne prev when cur - prev = 2 ->
                    KeepOne cur
                | SkipOne prev when cur - prev = 2 ->
                    KeepTwo(prev,cur)
                | _ ->
                    SkipOne cur)
            Head
            xl

    seq { 
        for x in xl' do
            match x with
            | KeepTwo(a,b) -> yield a; yield b
            | KeepOne b -> yield b
            | _ -> ()
    }

Answer 5

for completeness sake, I'll answer this with what I eventually came up with, based on the friendly suggestions in this thread.

The benefits of this approach are that it doesn't need Seq.distinct, which I believe is an improvement as it allows for duplicates. However, it still needs List.rev which doesn't make it the fastest. Nor is it the most succinct code (see comparison of solution in question itself).

let filterTwins l = 
    l 
    |> Seq.pairwise 
    |> Seq.fold (fun a (x, y) -> 
        if y - x = 2 then (if List.head a = x then y::a else y::x::a) 
        else a) [0]
    |> List.rev 
    |> List.tail