f# - 如何在 F# 中追加到列表而不是前置？

Question

在 F# 中添加列表有点烦人，因为一旦完成，您必须将其反转。有没有办法从一开始就直接建立一个列表？

Answer 1

如果需要将元素追加到末尾，可以使用称为DList. FSharpX 中有一个可用的实现。

但是，有一些与此相关的运行时开销（例如，请参阅此处的评论），因此我认为通过预先添加然后反转来构建列表通常会更有效。在函数式编程中这也是相当标准的事情 - 一开始可能看起来有点混乱，但在实现遍历列表的递归函数时，它是一种非常常见的“设计模式”，所以我不会试图避免它。

Answer 2

回顾您的原始代码，我认为您正在寻找的是使用List.foldBack而不是List.fold. 本质上，从列表的末尾而不是从列表的开头foldBack重复应用函数。folder它没有效率那么高，fold但最好使用foldBack并避免颠倒列表。

使用foldBack，您的累积函数将按如下folder方式应用于列表，其中 的初始参数是：x0::x1::...::xlastfolderinit

folder x0 (folder x1 ( ... (folder xlast init) ... ) )

参考fold

folder (... (folder (folder init x0) x1) ...) xlast

您的原始问题还有一些其他答案可以建议替代解决方案，但请坚持使用您的代码，在第一次实现中foldBack替换结果fold

let chunkOrig items chunkSize =
    let folder =
        fun x (result, chunk) ->
            if List.length chunk < chunkSize then
                (result, x::chunk)
            else
                (chunk::result, [x])
    let (a,b) = List.foldBack folder items ([], []) 
    b::a

这已经简单多了，因为所有的列表反转都消失了。它似乎有效。

> chunkOrig [1..10] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]]

但是，当您的列表没有分成相等的块时，它会出错，因为foldBack从最后一个元素开始。

> chunkOrig [1..11] 2;;
val it : int list list = [[1]; [2; 3]; [4; 5]; [6; 7]; [8; 9]; [10; 11]]

您需要做的是folder通过当前块中剩余的长度而不是块本身来参数化您的本地函数。

let chunk items chunkSize =
    let folder =
        fun x (result, lenLeft) ->
        if lenLeft > 0 then
            match result with
               | [] -> ([[x]], lenLeft-1)
               | r0::rtail -> ((x::r0)::rtail, lenLeft-1)
        else
            ([x]::result, chunkSize-1)
    let (result, lenLeft) = List.foldBack folder items ([], (List.length items) % chunkSize) 
    result

> chunk [1..10] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]]

> chunk [1..11] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]; [11]]

Answer 3

x像这样追加xs：

xs @ [x]

请注意，这是 O(n)。

Answer 4

前置和反转列表没有任何问题。您可以在单元素列表上使用 append ( @)，但这是一种代码异味。一种可容忍的（尾递归）方法是：

let appendSingle xs x =
    [ yield! xs
      yield x ]

以上所有解决方案都有 O(n) 的执行时间。对于您的用例，您可以保留一个私有ResizeArray以避免使用反向。这很好，因为可变性被隐藏了。比较这个函数

let filter f l = 
  let rec loop acc l =
    match l with 
    | [] -> List.rev acc                        
    | x::xs when f x -> loop (x::acc) xs  
    | x::xs -> loop acc xs
  loop [] l

与其更高效的对应物

let filter f l = 
  let rec loop (acc : ResizeArray<_>) l =
    match l with 
    | [] -> Seq.toList acc                        
    | x::xs when f x -> 
        acc.Add(x)  
        loop acc xs  
    | x::xs -> loop acc xs
  loop (ResizeArray()) l