F#中如何执行Seq.takeWhile + n项

huangapple go评论134阅读模式
英文:

How to do Seq.takeWhile + n items in F#

问题

这是对经典问题如何在F#中执行Seq.takeWhile + 一个项目的借鉴,将其扩展到在谓词返回false后提取n个项目的一般情况。

显而易见的基本解决方案可以基于Tomas的答案,他在IEnumerator<'T>上的递归循环中增加了一个额外的计数器,但我至少可以想到其他两种方法。

首先,有Seq.pairwise,由Be Brave Be Like Ukraine提出,可以根据需要复制多次;附加元组的开销可能会使其效率不高:

// n = 0的特殊情况
let takeWhile pred =
    Seq.map (fun t -> pred t, Some t)
    >> Seq.takeWhile fst
    >> Seq.choose snd

let takeWhile1 pred =
    Seq.map (fun t -> pred t, Some t)
    >> Seq.append (Seq.singleton (true, None))
    >> Seq.pairwise
    >> Seq.takeWhile (fst >> fst)
    >> Seq.choose (snd >> snd)

let takeWhile2 pred =
    Seq.map (fun t -> pred t, Some t)
    >> Seq.append (Seq.singleton (true, None))
    >> Seq.append (Seq.singleton (true, None))
    >> Seq.pairwise
    >> Seq.pairwise
    >> Seq.takeWhile (fst >> fst >> fst)
    >> Seq.choose (snd >> snd >> snd)

[1..7] |> takeWhile ((>=) 3) |> Seq.toList
// 结果: [1; 2; 3]
[1..7] |> takeWhile1 ((>=) 3) |> Seq.toList
// 结果: [1; 2; 3; 4]
[1..7] |> takeWhile2 ((>=) 3) |> Seq.toList
// 结果: [1; 2; 3; 4; 5]

另一种方法涉及使用Seq.tryHeadSeq.tail来分解序列。经过测试,我意识到这可能不是最佳选择,因为序列的元素被评估的次数呈二次增长。

let takeWhileN pred n source = 
    let rec aux i source = seq{
        match Seq.tryHead source with
        | Some x when pred x && i = 0 ->
            yield x
            yield! aux 0 (Seq.tail source)
        | Some x when i < n ->
            yield x
            yield! aux (i + 1) (Seq.tail source)
        | _ -> () }
    aux 0 source

[1..7] |> takeWhileN ((>=) 3) 0 |> Seq.toList
// 结果: [1; 2; 3]
[1..7] |> takeWhileN ((>=) 3) 1 |> Seq.toList
// 结果: [1; 2; 3; 4]
[1..7] |> takeWhileN ((>=) 3) 2 |> Seq.toList
// 结果: [1; 2; 3; 4; 5]

这是否可以改进?

英文:

This is piggybacking on the classic question how to do Seq.takeWhile + one item in F# by extending it to the general case of extracting n items after the predicate returns false.

The obvious bare-bone solution may be based on Tomas' answer to the original question by equipping the recursive loop on IEnumerator<'T> with an additional counter, but I can think of at least two other approaches.

First there's Seq.pairwise suggested by Be Brave Be Like Ukraine which could be replicated as often as needed; the overhead of the additional tuples will probably mean that it's not very efficient:

// Trivial case for n = 0
let takeWhile pred =
    Seq.map (fun t -> pred t, Some t)
    >> Seq.takeWhile fst
    >> Seq.choose snd

let takeWhile1 pred =
    Seq.map (fun t -> pred t, Some t)
    >> Seq.append (Seq.singleton (true, None))
    >> Seq.pairwise
    >> Seq.takeWhile (fst >> fst)
    >> Seq.choose (snd >> snd)

let takeWhile2 pred =
    Seq.map (fun t -> pred t, Some t)
    >> Seq.append (Seq.singleton (true, None))
    >> Seq.append (Seq.singleton (true, None))
    >> Seq.pairwise
    >> Seq.pairwise
    >> Seq.takeWhile (fst >> fst >> fst)
    >> Seq.choose (snd >> snd >> snd)

[1..7] |> takeWhile ((>=) 3) |> Seq.toList
// val it : int list = [1; 2; 3]
[1..7] |> takeWhile1 ((>=) 3) |> Seq.toList
// val it : int list = [1; 2; 3; 4]
[1..7] |> takeWhile2 ((>=) 3) |> Seq.toList
// val it : int list = [1; 2; 3; 4; 5]

The other involves deconstruction of the sequence by Seq.tryHead and Seq.tail. After testing I realize that this would be sub-optimal as the number of times the elements of the sequence get evaluated grows quadratically.

let takeWhileN pred n source = 
    let rec aux i source = seq{
        match Seq.tryHead source with
        | Some x when pred x && i = 0 ->
            yield x
            yield! aux 0 (Seq.tail source)
        | Some x when i < n ->
            yield x
            yield! aux (i + 1) (Seq.tail source)
        | _ -> () }
    aux 0 source

[1..7] |> takeWhileN ((>=) 3) 0 |> Seq.toList
// val it : int list = [1; 2; 3]
[1..7] |> takeWhileN ((>=) 3) 1 |> Seq.toList
// val it : int list = [1; 2; 3; 4]
[1..7] |> takeWhileN ((>=) 3) 2 |> Seq.toList
// val it : int list = [1; 2; 3; 4; 5]

Can this be improved upon?

答案1

得分: 2

你的解决方案非常出色。唯一需要注意的是,一旦你超过了谓词部分,你可以使用 Seq.truncate 而不是逐个产生项目。

let rec takeWhileN pred n source = seq {
    match Seq.tryHead source with
    | Some x when pred x ->
        yield x
        yield! takeWhileN pred n (Seq.tail source)
    | _ -> yield! Seq.truncate n source            
}
英文:

Your solution is very good. The only note is that once you're past the predicate, you can use Seq.truncate rather than yielding items one at a time.

let rec takeWhileN pred n source = seq {
    match Seq.tryHead source with
    | Some x when pred x ->
        yield x
        yield! takeWhileN pred n (Seq.tail source)
    | _ -> yield! Seq.truncate n source            
}

答案2

得分: 0

以下是翻译好的部分:

你也可以直接这样做

    let takeWhileN pred n source =
        let matches = source |> Seq.takeWhile pred |> Seq.length
        source |> Seq.truncate (matches + n)
英文:

You can also just be direct about it:

let takeWhileN pred n source =
    let matches = source |> Seq.takeWhile pred |> Seq.length
    source |> Seq.truncate (matches + n)

huangapple
  • 本文由 发表于 2023年3月12日 19:22:31
  • 转载请务必保留本文链接:https://go.coder-hub.com/75712764.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定