Фильтрация массива или списка по последовательным парам на основе соответствующего правила

Question

Это, вероятно, тривиально, и у меня есть решение, но я не доволен им.Каким-то образом (гораздо) более простые формы, похоже, не работают, и они запутываются в угловых случаях (либо первое, либо последнее совпадение пар в строке).

Чтобы упростить задачу, давайте определим правило соответствиякак любые два или более чисел с разницей в два .Пример:

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

Код, который я сейчас использую, выглядит так: он выглядит просто неряшливо и избыточно:

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

Я намеревалсясобственное оригинальное упражнение для экспериментирования с List.foldBack, большими списками и параллельным программированием (которое прошло хорошо), но в итоге мы связались с «легкой» частью ...

Руководство по ответам

• Последние Даниэля , 113 символов *, легко проследить, медленно
• 2-ой Kvb, 106 символов * (если я включу функцию), легко, но возвращаемозначение требует работы
• 2-е число Стивена , 397 символов *, длинная и сравнительно сложная, но самая быстрая
• Абель , 155 символов *, на основеДаниэль разрешает дубликаты (кстати, это не было необходимостью) и является относительно быстрым.

Было больше ответов, но я считаю, что вышеизложенные были наиболее отчетливыми.Надеюсь, я не обидел никого на чувства, приняв ответ Даниэля в качестве решения: каждое решение заслуживает того, чтобы быть выбранным ответом (!).

* подсчет, выполненный с именами функций как один символ

Answer 1

Будет ли это делать то, что вы хотите?

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

Это ужасно неэффективно, но вот еще один подход с использованием более встроенных функций:

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

Может быть, немного лучше:

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

Вот еще одно решение, в котором используется та же стратегия дискриминационного объединения, что и в моем другом ответе, но оно работает с последовательностями лениво, так что вы можете наблюдать, как эти близнецы (простые числа?) Переходят по мере их поступления:

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 3

Следующее решение в духе вашего собственного, но я использую различающее объединение, чтобы инкапсулировать аспекты алгоритма и немного царствовать в безумии:

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

Как насчет этого?

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]

Или, если все элементы вашего списка уникальны, вы можете сделать это:

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]

РЕДАКТИРОВАТЬ

Или вот еще одна альтернатива, которую я нахожу элегантной.Сначала определите функцию для разбиения списка на список групп последовательных элементов, удовлетворяющих предикату:

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)

Затем создайте свою функцию, собрав все результаты вместе, отбросив любые одиночные символы:

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 5

для полноты картины я отвечу на это тем, что в конце концов придумал, основываясь на дружественных предложениях в этой теме.

Преимущества этого подхода в том, что ему не нужен Seq.distinct, что, я считаю, является улучшением, поскольку допускает дублирование. Тем не менее, он все еще нуждается в List.rev, что не делает его самым быстрым. Это не самый лаконичный код (см. Сравнение рассматриваемого решения).

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