Getting constant length retrieve time constant with immutable lists in a functional programming context

Question

I am currently facing the problem of having to make my calculations based on the length of a given list. Having to iterate over all the elements of the list to know its size is a big performance penalty as I'm using rather big lists.

What are the suggested approaches to the problem?

I guess I could always carry a size value together with the list so I know beforehand its size without having to compute it at the call site but that seems a brittle approach. I could also define a own type of list where each node has as property its the lists' size but then I'd lose the leverage provided by my programming language's libraries for standard lists.

How do you guys handle this on your daily routine?

I am currently using F#. I am aware I can use .NET's mutable (array) lists, which would solve the problem. I am way more interested, though, in the purely immutable functional approach.

Answer 1

The built-in F# list type doesn't have any caching of the length and there is no way to add that in some clever way, so you'll need to define your own type. I think that writing a wrapper for the existing F# list type is probably the best option.

This way, you can avoid explicit conversions - when you wrap the list, it will not actually copy it (as in svick's implementation), but the wrapper can easily cache the Length property:

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

The best way to work with the wrapper is to use LengthList.ofList for creating LengthList from a standard F# list and to use LengthList.toList (or just the List) property before using any functions from the standard List module.

However, it depends on the complexity of your code - if you only need length in a couple of places, then it may be easier to keep it separately and use a tuple list<'T> * int.