f# - 如何在 F# 中编写高效的列表/序列函数？ (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可以找到 here看起来像这样:

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# 的不可变列表实际上是可变的，因为性能？我对此有点担心，因为我认为这是 F# 中的“要走的路”，所以使用了前置然后反向列表方法。

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

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

是否有使用函数式编程概念的此类问题的有效解决方案(特别是 mapFoldWhile 并且通常“提前退出”)，或者我是否必须切换到命令式解决方案/使用 Collections.Generics.List ?

Answer 1

大多数情况下，使用 List.rev是一个完全足够的解决方案。

您说得对，F# 核心库使用变异和其他肮脏的 hack 来从 F# 列表操作中挤出更多性能，但我认为那里进行的微优化并不是特别好的例子。 F# 列表函数几乎无处不在，因此它可能是一个很好的权衡，但在大多数情况下我不会遵循它。

使用以下命令运行您的函数:

let l = [ 1 .. 1000000 ]

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

当我在没有更改的情况下运行该函数时，我在第二行得到 ~240 毫秒。当我刚放下时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一旦退出条件发生就停止计算。