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 回答