haskell - 在函数式编程上下文中使用不可变列表获取恒定长度检索时间常数

Question

我目前面临的问题是必须根据给定列表的长度进行计算。由于我使用的列表相当大，因此必须迭代列表的所有元素才能知道其大小，这是一个很大的性能损失。

解决该问题的建议方法是什么？

我想我总是可以将大小值与列表一起携带，这样我就可以事先知道它的大小，而不必在调用站点计算它，但这似乎是一种脆弱的方法。我还可以定义一个自己的列表类型，其中每个节点都有其列表大小作为属性，但这样我就会失去我的编程语言的标准列表库提供的杠杆作用。

你们在日常生活中如何处理这个问题？

我目前正在使用 F#。我知道我可以使用.NET 的可变(数组)列表，这可以解决问题。不过，我对纯粹不可变的函数方法更感兴趣。

Answer 1

内置的 F# 列表类型没有任何长度缓存，并且无法以某种巧妙的方式添加它，因此您需要定义自己的类型。我认为为现有的 F# list 编写一个包装器type 可能是最好的选择。

这样，您可以避免显式转换 - 当您包装列表时，它实际上不会复制它(如在 svick 的实现中)，但包装器可以轻松缓存 Length属性:

open System.Collections

type LengthList<'T>(list:list<'T>) =
  let length = lazy list.Length
  member x.Length = length.Value
  member x.List = list
  interface IEnumerable with
    member x.GetEnumerator() = (list :> IEnumerable).GetEnumerator()
  interface seq<'T> with  //'
    member x.GetEnumerator() = (list :> seq<_>).GetEnumerator()

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module LengthList =
  let ofList l = LengthList<_>(l)
  let ofSeq s = LengthList<_>(List.ofSeq s)
  let toList (l:LengthList<_>) = l.List
  let length (l:LengthList<_>) = l.Length

使用包装器的最佳方法是使用 LengthList.ofList用于创建LengthList来自标准 F# 列表并使用 LengthList.toList (或只是 List )属性，然后再使用标准 List 中的任何函数模块。

但是，这取决于代码的复杂性 - 如果您只需要几个地方的长度，那么将其单独保留并使用元组 list<'T> * int 可能会更容易.