1

这可能是微不足道的，我确实有一个解决方案，但我对此并不满意。不知何故，（很多）更简单的形式似乎不起作用，并且在角落案例（第一个或最后一个匹配对）周围变得混乱。

为简单起见，我们将匹配规则定义为任何两个或多个相差为 2 的数字。例子：

> 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个字符*，易学，慢
  • Kvb 的第 2 个，106 个字符*（如果我包含该函数），很简单，但返回值需要工作
  • 斯蒂芬的第二部，397 个字符*，冗长而复杂，但最快
  • Abel 的，155 个字符*，基于 Daniel 的，允许重复（这不是必需的，顺便说一句）并且相对较快。

有更多的答案，但我相信以上是最明显的。希望我接受丹尼尔的答案作为解决方案不会伤害任何人的感情：每一个解决方案都应该成为选定的答案（！）。

* 以函数名作为一个字符进行计数

4

5 回答 5

2

这会做你想要的吗？

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
于 2011-02-23T21:21:55.203 回答
1

这个怎么样？

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]
于 2011-02-23T21:39:31.053 回答
1

以下解决方案本着您自己的精神，但我使用了一个有区别的联合来封装算法的各个方面并有点疯狂：

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
于 2011-02-23T23:07:04.257 回答
1

这是另一种解决方案，它使用与我的其他答案类似的区分联合策略，但它懒惰地适用于序列，因此您可以看到那些双胞胎（素数？）在它们到来时滚动：

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
            | _ -> ()
    }
于 2011-02-24T02:07:54.817 回答
0

为了完整起见，我将根据这个线程中的友好建议，用我最终想出的内容来回答这个问题。

这种方法的好处是它不需要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
于 2011-03-10T14:02:53.370 回答