F#中列表的实现如何工作？

Question

我很好奇列表模块/类型在F#中是如何工作的,特别是它是否优化了这个？

let xs = ["1"; "2"; "3"]

let ys = "0"::xs

let zs = ["hello"; "world"]@xs

我查看了一些来源https://github.com/fsharp/fsharp/blob/68e37d03dfc15f8105aeb0ac70b846f82b364901/src/fsharp/FSharp.Core/prim-types.fs#L3493似乎是相关领域.

我想知道是否xs在制作时被复制ys.

如果你只是元素,我会认为很容易指向现有的列表.

如果你是连接我想象它可能是不可能的,因为它需要改变列表的最后一个元素指向下一个元素？

如果有人可以从FSharp.Core中注释/粘贴代码片段,这将是理想的.

Answer 1

所以List的实现有点奇怪.它实际上是作为一个有区别的联盟实现的.从规格:

type 'T list =
| ([])  
| (::)  of 'T * 'T list 

因此,您可以将其::视为一个带有两个参数并创建元组的函数(由于它与列表大小无关,因此速度很快).

@更复杂.这是实施:

    let (@) l1 l2 = 
        match l1 with
        | [] -> l2
        | (h::t) -> 
        match l2 with
        | [] -> l1
        | _ -> 
          let res = [h] 
          let lastCons = PrivateListHelpers.appendToFreshConsTail res t 
          PrivateListHelpers.setFreshConsTail lastCons l2;
          res

这两个奇怪的函数基本上改变了列表的位置. appendToFreshConsTail复制列表并返回最后一个元素. setFreshConsTail然后更改最后一个元素,以便将其下一个元素设置为l2而不是[]加入列表.