函数式编程-F#中的cons运算符(::)

F#中的::运算符始终将元素添加到列表中。 列表中是否有运算符? 我猜想使用@运算符

[1; 2; 3] @ [4]

效率不如附加一个元素。

Max asked 2020-08-10T09:39:10Z
7个解决方案
46 votes

就像其他人说的那样,没有这样的运算符,因为这没有多大意义。 我实际上认为这是一件好事,因为它使人们更容易意识到操作效率不高。 在实践中,您不需要运算符-通常有更好的方式编写相同的内容。

典型场景:我认为您可能认为需要在元素末尾附加元素的典型场景是如此普遍,以至于对其进行描述可能很有用。

当您使用accumulator参数编写函数的尾部递归版本时,在最后添加元素似乎是必要的。 例如,列表的::函数的(低效率)实现如下所示:

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),这比逐一添加元素要有效得多。

Tomas Petricek answered 2020-08-10T09:39:35Z
27 votes

F#中的列表是单链的且不可变的。 这意味着在最前面的是O(1)(创建一个元素并将其指向现有列表),而在最后面的地方是O(N)(因为必须复制整个列表;您不能更改 现有的最终指针,则必须创建一个完整的新列表)。

如果您确实需要“将一个元素附加到后面”,则例如

l @ [42]

是这样做的方法,但这是代码的味道。

Brian answered 2020-08-10T09:40:04Z
13 votes

追加两个标准列表的成本与左侧列表的长度成正比。 特别是成本

xs @ [x]

hlist的长度成比例-这不是一个固定成本。

如果您想要一个具有固定时间追加的类似列表的抽象,则可以使用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 []

这个想法是,您可以从功能上将列表表示为从“其余元素”到“最终列表”的函数。 如果您要在查看任何元素之前先构建整个列表,则此方法非常有用。 否则,您将不得不处理附加的线性成本或完全使用其他数据结构。

Norman Ramsey answered 2020-08-10T09:40:38Z
5 votes

我猜测使用@运算符[...]效率不如附加一个元素。

如果是这样,则差异可以忽略不计。 附加单个项目和将列表连接到末尾都是O(n)操作。 事实上,我想不出@必须做的一件事情,而单项附加函数却做不到。

sepp2k answered 2020-08-10T09:41:03Z
3 votes

也许您想使用其他数据结构。 我们在fsharpx中有双端队列(或简称为“ Deques”)。 您可以在[http://jackfoxy.com/double-ended-queues-for-fsharp]中了解有关它们的更多信息。

forki23 answered 2020-08-10T09:41:23Z
1 votes

效率(或缺乏效率)来自遍历列表以查找最终元素。 因此,使用[4]声明新列表对于除最琐碎的情况以外的所有情况都是可以忽略的。

Brian Agnew answered 2020-08-10T09:41:43Z
0 votes

尝试使用双端队列而不是列表。 我最近在FSharpx.Core中添加了4个版本的双端队列(冈崎的拼写)(可通过NuShar获取。FSharpx.Core.Datastructures源代码)。 请参阅有关为F#使用双端队列的双端队列文章。

我已经向F#团队建议使用cons运算符::和活动模式识别符可用于带有头/尾签名的其他数据结构。3

Jack Fox answered 2020-08-10T09:42:08Z
translate from https://stackoverflow.com:/questions/2483131/cons-operator-in-f