如何附加到F#中的列表而不是前置？

Question

在F#中列出一个列表有点烦人,因为一旦你完成了你必须扭转它.有没有办法从一开始就建立一个列表？

Answer 1

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

但是,有一些与此相关的运行时开销(例如,请参见此处的注释),因此我认为通过预先设置然后反转来构建列表通常会更有效.它在函数式编程中也是非常标准的事情 - 起初看起来有点令人困惑,但是当实现遍历列表的递归函数时,它是一种非常常见的"设计模式",所以我不会试图避免它.

Answer 2

前置和反转列表没有任何问题。@您可以在单元素列表上使用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