CODEWITHSUNDEEP
f#
Simon V.
Simon V.

Reputation: 1485

Will List.map allocate a new List every time?

Let's consider the following lists :

// 2 2 2 1 1 1
let xs = [2;2;2;1;1;1]

// 2 2 2 1 1 1
let xs' = List.map (fun x -> x) list

// 4 4 4 1 1 1
let xs'' = List.map (fun x -> x * x) list

Will List.map allocate a new list in the second case ? In the third case, will xs share the tail [1;1;1] with xs'' ?

Upvotes: 2

Views: 187

Answers (2)

Tomasz Maczyński
Tomasz Maczyński

Reputation: 973

As John pointed out, optimization that you mentioned are not performed. If you really need it (which is highly unlikely), you can write your own version of map which shares the tail of a list, something like:

/// Returns a copy of 'a' which shares a common suffix with 'b'.
/// 'a' and 'b' must me of equal length.
let shareSuffixWith (a : 'a list) (b : 'a list) : 'a list =
    let discardLastNElements (n: int) (li : 'a list) = 
        List.take (li.Length - n) li
    let commonSuffix = 
        let zippedLists = List.zip a b
        let lastDifferentElemIndex = 
            List.tryFindIndexBack (fun (e1, e2) -> e1 <> e2) zippedLists
        match lastDifferentElemIndex with
        | None -> b
        | Some(index) -> List.skip (index+1) b
    let aPreffix = discardLastNElements commonSuffix.Length a
    aPreffix @ commonSuffix

/// Maps elements of a list using a mapping and shares 
/// common tail between input list and the result.
let mapAndShareSuffix (mapping :'T -> 'T) (li : 'T list) : 'T list = 
    let resultOfMap = List.map mapping li
    shareSuffixWith resultOfMap li

Note that:

  • this implementation will perform more memory allocations then simply using List.map but some part of memory will be freed during Garbage Collection.

  • F# lists does not take much space - only twice the size of a pointer per one element so the amount of memory that you gain by sharing a tail is minimal in most cases

  • sharing list's tail takes processing and GC time

  • the implementation above is sub-optimal and not idiomatic

Upvotes: 2

John Palmer
John Palmer

Reputation: 25516

The standard library tends to use simple implementations of this type of function.

As a result, this type of optimization isn't done.

The implementation can be found here: https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/local.fs#L85

Upvotes: 5

Related Questions