如何在F#中编写高效的list/seq函数？(mapFoldWhile)

Question

我正在尝试编写一个泛型mapFoldWhile函数,它只是mapFold需要state成为一个option并在遇到None状态时立即停止.

我不想使用,mapFold因为它将转换整个列表,但我希望它一旦None找到无效状态(即)就停止.

这是我的第一次尝试:

let mapFoldWhile (f : 'State option -> 'T -> 'Result * 'State option) (state : 'State option) (list : 'T list) =
  let rec mapRec f state list results =
    match list with 
    | [] -> (List.rev results, state)
    | item :: tail -> 
      let (result, newState) = f state item
      match newState with 
      | Some x -> mapRec f newState tail (result :: results)
      | None -> ([], None)
  mapRec f state list []

该List.rev激怒了我,因为练习的要点是要提前退出,建设一个新的列表应该会更慢.

所以我抬头看看F#的自己map做了什么,这是:

let map f list = Microsoft.FSharp.Primitives.Basics.List.map f list

Microsoft.FSharp.Primitives.Basics.List.map可以在这里找到不祥之物,看起来像这样:

let map f x = 
    match x with
    | [] -> []
    | [h] -> [f h]
    | (h::t) -> 
        let cons = freshConsNoTail (f h)
        mapToFreshConsTail cons f t
        cons

该consNoTail材料也是在这个文件中:

// optimized mutation-based implementation. This code is only valid in fslib, where mutation of private
// tail cons cells is permitted in carefully written library code.
let inline setFreshConsTail cons t = cons.(::).1 <- t
let inline freshConsNoTail h = h :: (# "ldnull" : 'T list #)

所以我觉得F#的不可变列表实际上是可变的,因为性能？我有点担心这个,使用了prepend-then-reverse列表方法,因为我认为这是F#中的"方法".

我对F#或函数式编程一般都不是很有经验,所以也许(可能)创建一个新mapFoldWhile函数的整个想法是错误的,但那我该做什么呢？

我经常发现自己处于需要"提前退出"的情况,因为收集项目是"无效的",我知道我不必看其余的.我正在使用List.pick或Seq.takeWhile在某些情况下,但在其他情况下,我需要做更多(mapFold).

是否有一种有效的解决方案来解决这类问题(mapFoldWhile特别是"早期退出")和函数式编程概念,还是我必须切换到命令式解决方案/使用Collections.Generics.List？

Answer 1

在大多数情况下,使用List.rev是一个非常充分的解决方案

你是对的,F#核心库使用变异和其他脏的黑客来从F#list操作中挤出更多的性能,但我认为那里的微优化并不是特别好的例子.F#list函数几乎在所有地方使用,因此它可能是一个很好的权衡,但在大多数情况下我不会遵循它.

使用以下命令运行您的功能:

let l = [ 1 .. 1000000 ]

#time 
mapFoldWhile (fun s v -> 0, s) (Some 1) l

当我在没有更改的情况下运行该函数时,我在第二行得到~240ms.当我只是丢弃List.rev(以便以其他顺序返回数据)时,我大约需要190毫秒.如果你真的经常调用这个函数,这很重要,那么你必须使用变异(实际上,你自己的可变列表类型),但我认为这很少值得.

对于一般的"退出早"的问题,你可以经常写代码的组成Seq.scan和Seq.takeWhile.例如,假设您要对序列中的数字求和,直到达到1000.您可以写:

input
|> Seq.scan (fun sum v -> v + sum) 0
|> Seq.takeWhile (fun sum -> sum < 1000)

使用Seq.scan生成一个在整个输入上的和的序列,但由于这是延迟生成的,Seq.takeWhile因此一旦退出条件发生就停止计算.