19

我想编写一个函数，它使用谓词过滤序列，但结果还应该包括谓词返回 false 的第一项。

如果在 F# 中有一个 break 关键字，逻辑将是这样的

let myFilter predicate s =
    seq {
        for item in s do
            yield item
            if predicate item then
                break
    }

我尝试了 Seq.takeWhile 和 Seq.skipWhile 的组合，如下所示：

Seq.append 
    (Seq.takeWhile predicate s) 
    (Seq.skipWhile predicate s |> Seq.take 1)

...但问题是与谓词匹配的第一项在 takeWhile 和 skipWhile 之间丢失

另请注意，输入序列是惰性的，因此任何消耗该序列并随后做出决定的解决方案都是不可行的。

有任何想法吗？

谢谢！

编辑：非常感谢所有的答案！没想到这么快就有这么多回复。我很快就会看看他们中的每一个。现在我只想提供更多背景信息。考虑以下实现 shell 的编码 kata：

let cmdProcessor state = function
    | "q" -> "Good bye!"
    | "h" -> "Help content"
    | c -> sprintf "Bad command: '%s'" c

let processUntilQuit =
    Seq.takeWhile (fun cmd -> cmd <> "q")

let processor = 
    processUntilQuit
    >> Seq.scan cmdProcessor "Welcome!"

module io =
    let consoleLines = seq { while true do yield System.Console.ReadLine () }

    let display : string seq -> unit = Seq.iter <| printfn "%s" 

io.consoleLines |> processor|> io.display

printf "Press any key to continue..."
System.Console.ReadKey ()|> ignore

这个实现的问题是它不打印“再见！” 输入命令 q 时。

我想要做的是实现函数processUntilQuit以便它处理直到“q”的所有命令，包括“q”。

4

11 回答 11

18

缺乏对breakin 计算表达式的支持有点烦人。它不适合 F# 使用的模型（这就是不支持它的原因），但在这种情况下它会非常有用。

如果您只想对序列进行一次迭代来实现这一点，那么我认为最干净的解决方案是只使用序列的底层结构并将其编写为递归循环，使用IEnumerator<'T>

这相当短（与此处的其他解决方案相比），而且代码也非常清晰：

let myFilter predicate (s:seq<_>) = 
  /// Iterates over the enumerator, yielding elements and
  /// stops after an element for which the predicate does not hold
  let rec loop (en:IEnumerator<_>) = seq {
    if en.MoveNext() then
      // Always yield the current, stop if predicate does not hold
      yield en.Current
      if predicate en.Current then
        yield! loop en }

  // Get enumerator of the sequence and yield all results
  // (making sure that the enumerator gets disposed)
  seq { use en = s.GetEnumerator()
        yield! loop en }
于 2012-09-24T12:17:50.890 回答
5

不要真正了解您的解决方案有什么问题。

两个小修正：

(1) 使用序列表达式以提高可读性。

(2)在输入序列为空的情况下使用Seq.truncate代替。Seq.take

let myFilter predicate s = 
    seq { yield! Seq.takeWhile predicate s
          yield! s |> Seq.skipWhile predicate |> Seq.truncate 1 }
于 2012-09-24T11:30:11.060 回答
2 
let duplicateHead xs = seq { yield Seq.head xs; yield! xs }
let filter predicate xs =
    xs
    |> duplicateHead
    |> Seq.pairwise
    |> Seq.takeWhile (fst >> predicate)
    |> Seq.map snd

的替代版本duplicateHead，以防您不喜欢此处的计算表达式：

let duplicateHead' xs =
    Seq.append 
        (Seq.head xs)
        xs

这种方法基于构建当前元素和下一个元素的元组。predicate正在应用于当前元素，但会返回以下元素。

注意：对于第一个元素失败的情况是不安全的。predicate为了使其正常工作，您必须duplicateHead通过添加一个肯定会通过predicate.

于 2012-09-24T11:03:51.510 回答
1

另一个较晚的答案，但它是“功能性的”，简单并且不会读取结果序列中最后一个元素之后的任何元素。

let myFilter predicate =
    Seq.collect (fun x -> [Choice1Of2 x; Choice2Of2 (predicate x)])
    >> Seq.takeWhile (function | Choice1Of2 _ -> true | Choice2Of2 p -> p)
    >> Seq.choose (function | Choice1Of2 x -> Some x | Choice2Of2 _ -> None)
于 2019-07-03T20:44:17.903 回答
0

好一点的。:)

let padWithTrue n xs = seq { for _ in 1..n do yield true; done; yield! xs }
let filter predicate n xs =
    let ys = xs |> Seq.map predicate |> padWithTrue n
    Seq.zip xs ys
    |> Seq.takeWhile snd
    |> Seq.map fst

这需要一个附加参数n，该参数定义要添加多少个附加元素。

注意：小心单行padWithTrue（done关键字）

于 2012-09-24T11:49:34.623 回答
0

我猜你想要什么直到：

let takeUntil pred s =
  let state = ref true
  Seq.takeWhile (fun el ->
    let ret= !state
    state := not <| pred el
    ret
    ) s
于 2014-07-26T05:04:47.740 回答
0

丑陋的功能解决方案:)：

let rec myFilter predicate =
        Seq.fold (fun acc s ->
            match acc with
                | (Some x, fs) -> 
                    match predicate s with
                        | true -> (Some x, fs @ [s])
                        | false -> (Some x, fs)
                | (_, fs) ->
                    match predicate s with
                        | true -> (None, fs @ [s])
                        | false -> (Some s, fs))
            (None, [])

你最终得到元组，其中第一个元素包含源列表中第一个不匹配元素的选项，第二个元素包含过滤列表。

丑陋的功能懒惰解决方案（对不起，我第一次没有正确阅读您的帖子）：

let myFilterLazy predicate s =
        let rec inner x =
            seq {
                match x with
                    | (true, ss) when ss |> Seq.isEmpty = false ->
                        let y = ss |> Seq.head
                        if predicate y = true then yield y
                        yield! inner (true, ss |> Seq.skip 1)
                    | (_, ss) when ss |> Seq.isEmpty = false ->
                        let y = ss |> Seq.head
                        if predicate y = true then
                            yield y
                            yield! inner (false, ss |> Seq.skip 1)
                        else
                            yield y
                            yield! inner (true, ss |> Seq.skip 1)
                    | _ -> 0.0 |> ignore
            }

        inner (false, s)

我在 F# 中的流利程度不足以使匹配中的终止大小写看起来不错，也许某些 F# 大师会有所帮助。

编辑：受 Tomas Petricek 启发的不那么丑的纯 F# 解决方案 答案：

let myFilterLazy2 predicate s =
        let rec inner ss = seq {
            if Seq.isEmpty ss = false then
                yield ss |> Seq.head
                if ss |> Seq.head |> predicate then
                    yield! ss |> Seq.skip 1 |> inner
        }

        inner s
于 2012-09-24T10:39:23.820 回答
0

丑陋的非功能性解决方案

let myfilter f s =
    let failed = ref false
    let newf = fun elem -> match !failed with 
                           |true -> 
                               failed := f elem
                               true
                           |false->false
    Seq.takeWhile newf s
于 2012-09-24T09:55:06.413 回答
0

这已经很老了，但我认为我会做出贡献，因为其他解决方案没有提出这个建议......

使用Seq.scan建立一个包含两个元素的谓词结果堆栈并简单地获取表示前一个元素的谓词结果的堆栈底部是true什么？（注意，没有测试过这段代码）

Seq.scan (fun (a,b,v) e -> (pred e, a, Some e)) (true, true, None )
>> Seq.takeWhile (fun (_,b,_) -> b)
>> Seq.map (fun (_,_,c) -> c)
于 2017-11-14T17:03:14.740 回答
0

我知道这是一个老问题。但是还有一个更实用的解决方案。

尽管如此，老实说，对于这个问题，我更喜欢Tomas Petricek 提出的更为迫切的解决方案。

let takeWhileAndNext predicate mySequence =
    let folder pred state element =
        match state with
            | Some (_, false) ->
                None
            | _ ->
                Some (Some element, pred element)
    let initialState = Some (None, true)
    Seq.scan (folder predicate) initialState mySequence |> Seq.takeWhile Option.isSome
                                                        |> Seq.map Option.get
                                                        |> Seq.map fst
                                                        |> Seq.filter Option.isSome
                                                        |> Seq.map Option.get

在倒数第二行中，|> Seq.filter Option.isSome可以替换为，因为除了match|> Seq.tail之外没有其他状态。initialStateSome (None, _)

于 2017-12-18T17:33:59.133 回答
0

自从提出问题以来，我知道它的年龄，但我不得不处理类似但更通用的问题，我希望有人会发现我的解决方案很有用。

这个想法是在闭包中捕获枚举器，然后返回一个迭代原始序列其余部分的函数。此函数有一个布尔参数 - 是否包含当前元素（OP 的情况）

/// allows fetching elements from same sequence
type ContinueSequence<'a> (xs: 'a seq) =

    let en = xs.GetEnumerator()

    member _.Continue (includeCurrent: bool) =
        let s = seq { while en.MoveNext() do yield en.Current }
        let c = seq { en.Current }
        if includeCurrent then
            Seq.append c s
        else
            s

    interface IDisposable with 
        member _.Dispose() =
            en.Dispose()

这个问题的实际答案是：

use seq = new ContinueSequence a 
let result = Seq.append
   seq.Continue(false) |> Seq.takeWhile(predicate) 
   seq.Continue(true) |> Seq.take(1)  //include element which breaks predicate

更通用的例子

/// usage example:
let a = seq [1; 2; 3; 4; 5; 6; 7]

use seq = new ContinueSequence<_>(a)
let s1 = seq.Continue(false) |> Seq.takeWhile((>) 3) // take 1 and 2, 3 is current
let s2 = seq.Continue(true) |> Seq.take(2)    // take 3 and 4
let s3 = seq.Continue(false) |> Seq.skip(1)   // skip 5

let s = 
    s1 
    |> Seq.append <| s2 
    |> Seq.append <| s3 
    |> Seq.toList

// s = [1; 2; 3; 4; 6; 7]
于 2020-04-26T07:25:25.407 回答