英文:
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.tryHead
和Seq.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)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论