commonPrefixLength

lib.lists.commonPrefixLength

Docs pulled from | This Revision | 20 minutes ago

Nixpkgs manual

Returns the length of the common prefix of two lists, i.e. the number of leading elements that are pairwise equal.

This is more efficient than length (commonPrefix a b) because it avoids allocating an intermediate list.

Type

commonPrefixLength :: [a] -> [a] -> Int

Examples

`lib.lists.commonPrefixLength` usage example

commonPrefixLength [ 1 2 3 4 5 6 ] [ 1 2 4 8 ]
=> 2
commonPrefixLength [ 1 2 3 ] [ 1 2 3 4 5 ]
=> 3
commonPrefixLength [ 1 2 3 ] [ 4 5 6 ]
=> 0

Noogle detected

Implementation

The following is the current implementation of this function.

commonPrefixLength =
    list1: list2:
    let
      # Zip the lists together into a list of booleans whether each element matches
      matchings = zipListsWith (fst: snd: fst != snd) list1 list2;
      # Find the first index where the elements don't match,
      # which will then also be the length of the common prefix.
      # If all elements match, we fall back to the length of the zipped list,
      # which is the same as the length of the smaller list.
    in
    findFirstIndex id (length matchings) matchings;