在F#中的cons运算符(::)

Question

F#中的::运算符始终将元素添加到列表中.是否有运营商附加到列表中？我猜是使用@运算符

[1; 2; 3] @ [4]

效率低于附加一个元素.

Answer 1

正如其他人所说,没有这样的运营商,因为它没有多大意义.我实际上认为这是一件好事,因为它使人们更容易意识到操作效率不高.在实践中,您不应该需要操作员 - 通常有更好的方法来编写相同的东西.

典型场景:我认为您可能认为需要将元素附加到末尾的典型场景非常常见,因此描述它可能很有用.

当您使用accumulator参数编写函数的尾递归版本时,添加元素似乎是必要的.例如filter,列表函数的(低效)实现看起来像这样:

let filter f l = 
  let rec filterUtil acc l =
    match l with 
    | [] -> acc
    | x::xs when f x -> filterUtil (acc @ [x]) xs
    | x::xs -> filterUtil acc xs
  filterUtil [] l

在每个步骤中,我们需要将一个元素追加到累加器(它存储要作为结果返回的元素).可以轻松修改此代码以使用::运算符,而不是将元素附加到acc列表的末尾:

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

在(2)中,我们现在将元素添加到累加器的前面,当函数即将返回结果时,我们反转列表(1),这比逐个附加元素要高效得多.

Answer 2

F#中的列表是单链接且不可变的.这意味着在前面进行的是O(1)(创建一个元素并让它指向现有列表),而后面的snocing是O(N)(因为必须复制整个列表;你不能改变它现有的最终指针,你必须创建一个全新的列表).

如果你确实需要"向后面添加一个元素",那么例如

l @ [42]

是这样做的方式,但这是代码气味.

Answer 3

附加两个标准列表的成本与左侧列表的长度成比例.特别是成本

xs @ [x]

与长度xs成正比- 它不是恒定成本.

如果你想要一个带有常量时间附加的类似列表的抽象,你可以使用John Hughes的函数表示,我将调用它hlist.我将尝试使用OCaml语法,我希望它与F#足够接近:

type 'a hlist = 'a list -> 'a list   (* a John Hughes list *)
let empty : 'a hlist = let id xs = xs in id
let append xs ys = fun tail -> xs (ys tail)
let singleton x = fun tail -> x :: tail
let cons x xs = append (singleton x) xs
let snoc xs x = append xs (singleton x)
let to_list : 'a hlist -> 'a list = fun xs -> xs []

我们的想法是,您在功能上将列表表示为从"其余元素"到"最终列表"的函数.如果要在查看任何元素之前构建整个列表,这将创建.否则,您将不得不处理线性成本的追加或完全使用其他数据结构.

Answer 4

我猜测使用@ operator [...]效率低于附加一个元素.

如果是,那将是一个微不足道的差异.附加单个项目并将列表连接到末尾都是O(n)操作.事实上,我无法想到一件@必须做的事情,单项附加功能不会.