如何在F#中将元素添加到列表末尾而不是开头？

Question

在F#中，列表的前置操作有些令人烦恼，因为一旦完成，您必须将其反转。是否有一种从开头直接构建列表的方法？

- Trident D'Gao

---

了解你所尝试做的事情的背景可能会有所帮助。 - TooTone

请问我在对列表进行分块时做错了什么？ - Trident D'Gao

Answer 1

如果您需要在末尾附加元素，可以使用称为“DList”的类型。在FSharpX中提供了一种实现方式，请参见此处。

然而，与此相关的运行时开销比较大（例如，请参见这里的评论），因此我认为通过向列表前面添加元素，然后再反转列表通常会更有效率。这也是函数式编程中非常标准的做法 - 虽然一开始可能看起来有点混乱，但在实现遍历列表的递归函数时，这是一个非常普遍的“设计模式”，所以不要试图避免它。

- Tomas Petricek

Answer 2

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

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

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

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

- pad

---

为什么你说使用 append (@) 与单元素列表是一种代码异味？在我看来，这是一个完全有效的方法。你的 appendSingle 函数基本上与 xs @ [x] 具有相同的性能特征，但以一种更复杂的方式实现。 - Gustavo Guerra

我应该说这两个表达都不太合适，但第二个由于尾递归是可以容忍的。 - pad

Answer 3

将xs添加x，可以像这样：

xs @ [x]

请注意，这是O(n)的时间复杂度。

- J D

---

也许 F# 像 Haskell 一样有 DList，所以你可以获得 O(1) 的追加操作？ - Peaker

我相信有一些库实现了具有附加和可连接列表的列表，但在现实世界中基本上没有这方面的需求。 - J D

Answer 4

回顾您的原始代码，我认为您要使用List.foldBack而不是List.fold。本质上，foldBack从列表末尾开始重复应用folder函数，而不是从列表开头开始。它不像fold那样高效，但最好使用foldBack并避免翻转列表。

使用foldBack，将累加函数folder应用于列表x0::x1::...::xlast，其中folder的初始参数为init：

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

参见 fold

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

您的原始问题有一些其他答案提供了替代解决方案，但如果坚持使用您的代码，将 fold 替换为 foldBack 将得到第一个实现。

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]]

- TooTone