29 lines
1.1 KiB
Nix
29 lines
1.1 KiB
Nix
|
# binaryMerge :: (b -> b -> b) -> [b] -> b | null
|
||
|
|
merge:
|
||
|
|
list:
|
||
|
|
|
||
|
|
let
|
||
|
|
# `binaryMerge start end` merges the elements at indices `index` of `list` such that `start <= index < end`
|
||
|
|
# Type: Int -> Int -> b
|
||
|
|
binaryMerge' = start: end:
|
||
|
|
# assert start < end; # Invariant
|
||
|
|
if end - start >= 2 then
|
||
|
|
let
|
||
|
|
# If there's at least 2 elements, split the range in two, recurse on each part and merge the result
|
||
|
|
# The invariant is satisfied because each half will have at least 1 element
|
||
|
|
firstHalf = binaryMerge' start (start + (end - start) / 2);
|
||
|
|
secondHalf = binaryMerge' (start + (end - start) / 2) end;
|
||
|
|
in merge firstHalf secondHalf
|
||
|
|
else
|
||
|
|
# Otherwise there will be exactly 1 element due to the invariant, in which case we just return it directly
|
||
|
|
builtins.elemAt list start;
|
||
|
|
in
|
||
|
|
if list == [ ] then
|
||
|
|
# Calling binaryMerge as below would not satisfy its invariant
|
||
|
|
null
|
||
|
|
else
|
||
|
|
binaryMerge' 0 (builtins.length list)
|
||
|
|
|
||
|
|
# Source: taken and modified from
|
||
|
|
# https://github.com/NixOS/nixpkgs/blob/3cae63521d93eb2fb0aba28218ca9b00150ffdc1/lib/attrsets.nix#L1488-L1507
|