rec {
  inherit true false null functionArgs typeOf seq deepSeq bitAnd bitOr bitXor floor ceil; # from the minimal prelude

  abort = _: null null; # we ignore the provided message
  throw = abort; # same here

  head = xs: (__mn_list_match xs).head;
  tail = xs: (__mn_list_match xs).tail;

  __mn_matchAttr = f: as: f (__mn_attr_match as);
  __mn_matchList = f: xs: f (__mn_list_match xs);
  __mn_matchString = f: s: f (__mn_string_match s);

  __mn_foldr = op: nul:
    __mn_matchList ({ head, tail, empty }:
      if empty then nul else op head (__mn_foldr op nul tail));

  # foldl' should really be strict. But if we do that (using seq), the
  # complexity of this function suddenly morphs from linear to
  # exponential, which is way worse than not actually being strict.
  foldl' = op: nul:
    __mn_matchList
      ({ head, tail, empty }:
        if empty then nul else
        let v = op nul head; in
        seq v (foldl' op v tail));
  map = f:
    __mn_matchList ({ head, tail, empty }:
      if empty then [ ] else [ (f head) ] ++ map f tail);
  elem = x: any (y: x == y);
  elemAt = xs: n: assert n >= 0;
    let go = xs: n: if n == 0 then head xs else go (tail xs) (n - 1);
    in go xs n;
  length = __mn_matchList ({ head, tail, empty }:
    if empty then 0 else 1 + length tail);
  sort = __mn_mergesort;
  any = f: __mn_matchList ({ head, tail, empty }: !empty && (f head || any f tail));
  all = f: __mn_matchList ({ head, tail, empty }: !empty -> (f head && all f tail));
  concatLists =
    __mn_matchList ({ head, tail, empty }:
      if empty then [ ] else head ++ concatLists tail);
  concatMap = f: xss: concatLists (map f xss);
  concatStringsSep = sep:
    __mn_matchList ({ head, tail, empty }:
      if empty then "" else if tail == [ ] then head
      else head + sep + concatStringsSep sep tail);
  filter = f:
    __mn_matchList ({ head, tail, empty }:
      if empty then [ ] else (if f head then [ head ] else [ ]) ++ filter f tail);
  groupBy = f: xs:
    let update = x: acc: acc // { ${f x} = [ x ] ++ (acc.${f x} or [ ]); };
    in __mn_foldr update { } xs;
  partition = f: groupBy (x: if f x then "right" else "wrong");

  hasAttr = x: as: as ? ${x};
  getAttr = x: as: as.${x};
  attrNames = __mn_matchAttr ({ key, tail, empty, ... }:
    if empty then [ ] else [ key ] ++ attrNames tail);
  attrValues = __mn_matchAttr ({ head, tail, empty, ... }:
    if empty then [ ] else [ head ] ++ attrValues tail);
  mapAttrs = f: __mn_matchAttr ({ key, head, tail, empty }:
    if empty then { } else
    mapAttrs f tail // { ${key} = f key head; });
  removeAttrs = __mn_foldr (x: as': __mn_attr_delete as' x);
  zipAttrsWith = f: ass: mapAttrs f (__mn_zipAttrs ass);
  catAttrs = x:
    __mn_matchList ({ head, tail, empty }:
      if empty then [ ]
      else (if head ? ${x} then [ head.${x} ] else [ ]) ++ catAttrs x tail);
  listToAttrs =
    __mn_foldr (attr: as': as' // { ${attr.name} = attr.value; }) { };
  intersectAttrs = e1: e2:
    __mn_matchAttr
      ({ key, head, tail, empty }:
        if empty then { } else
        (if e2 ? ${key} then { ${key} = e2.${key}; } else { }) //
        intersectAttrs tail (__mn_attr_delete e2 key))
      e1;

  lessThan = x: y: x < y; # documentation is misleading, not only for numbers
  add = x: y: x + y;
  mul = x: y: x * y;
  div = x: y: x / y;
  sub = x: y: x - y;
  genList = gen: n:
    let
      aux = off: if off >= n then [ ] else
      [ (gen off) ] ++ aux (off + 1);
    in
    aux 0;

  __mn_genericClosure = { operator, seen, startSet }:
    __mn_matchList
      ({ head, tail, empty }:
        if empty then [ ] else
        if seen head.key
        then __mn_genericClosure { inherit operator seen; startSet = tail; }
        else [ head ] ++ __mn_genericClosure {
          inherit operator;
          seen = k: k == head.key || seen k;
          startSet = tail ++ operator head;
        })
      startSet;
  genericClosure = { operator, startSet }:
    __mn_genericClosure { inherit operator startSet; seen = _: false; };

  isAttrs = e: typeOf e == "set";
  isBool = e: typeOf e == "bool";
  isFloat = e: typeOf e == "float";
  isFunction = e: typeOf e == "lambda";
  isInt = e: typeOf e == "int";
  isList = e: typeOf e == "list";
  isNull = e: typeOf e == "null";
  isString = e: typeOf e == "string";

  toString = e:
    if isAttrs e then
      if e ? __toString then e.__toString e else e.outPath
    else if isBool e then
      if e then "1" else ""
    else if isFloat e then
      __mn_float_toString e
    else if isInt e then
      __mn_int_toString e
    else if isList e then
      concatStringsSep " " (map toString e)
    else if isNull e then
      ""
    else if isString e then
      e
    else abort null;

  stringLength =
    __mn_matchString ({ head, tail, empty }:
      if empty then 0 else 1 + stringLength tail);

  substring = start: assert start >= 0; len:
    __mn_matchString ({ head, tail, empty }:
      if empty || len == 0 then "" else
      if start > 0
      then substring (start - 1) len tail
      else head + substring 0 (len - 1) tail);

  replaceStrings = from: to: s:
    __mn_matchList
      ({ head, tail, empty }:
        let from = if empty then [ ] else [ head ] ++ tail; in
        __mn_matchList
          ({ head, tail, empty }:
            let to = if empty then [ ] else [ head ] ++ tail; in
            assert length from == length to;
            __mn_strings_replace from to s)
          to)
      from;

  __mn_strings_replace = subsFrom: subsTo: s:
    let go = __mn_strings_replace subsFrom subsTo; in
    __mn_strings_replace_aux go subsFrom subsTo s;

  __mn_strings_replace_aux = go: subsFrom: subsTo: s:
    __mn_matchList
      ({ head, tail, empty }:
        if empty
        then
          __mn_matchString
            ({ head, tail, empty }: if empty then "" else head + go tail)
            s
        else
          let subFrom = head; subsFrom' = tail; in
          __mn_matchList
            ({ head, tail, ... }:
              let subTo = head; subsTo' = tail; in
              if subFrom == ""
              then
              # We can only ask ourselves why, but it is so -- in Nix:
              #   replaceStrings ["" "a"] ["X" "_"] "asdf" ~> "XaXsXdXfX"
              # and so we emulate this 'behavior'
                subTo + __mn_matchString
                  ({ head, tail, empty }:
                    if empty then "" else head + go tail)
                  s
              else
                ({ ok, rest }:
                  if ok
                  then subTo + go rest
                  else __mn_strings_replace_aux go subsFrom' subsTo' s)
                  (__mn_string_chopPrefix subFrom s))
            subsTo)
      subsFrom;

  __mn_string_chopPrefix = prefix: s:
    __mn_matchString
      ({ head, tail, empty }:
        if empty then { ok = true; rest = s; } else
        let prefix = head; prefix' = tail; in __mn_matchString
          ({ head, tail, empty }:
            if empty || prefix != head then { ok = false; rest = null; } else
            __mn_string_chopPrefix prefix' tail)
          s)
      prefix;

  __mn_string_drop = n: s:
    if n <= 0 then s else
    __mn_matchString
      ({ tail, empty, ... }:
        if empty then "" else
        __mn_string_drop (n - 1) tail)
      s;

  __mn_float_toString = x:
    let
      sign = x < 0;
      abs = __mn_abs x;
      int = floor abs;
      dec = __mn_nearestEven ((abs - int) * 1000000);
    in
    (if sign then "-" else "") +
    __mn_int_toString int + "." + __mn_int_toString dec;
  __mn_int_toString = x: (if x < 0 then "-" else "") +
    (
      let d10 = __mn_quotRem (__mn_abs x) 10; in
      (if d10.quot != 0 then toString d10.quot else "") +
        (if d10.rem == 0 then "0" else
        if d10.rem == 1 then "1" else
        if d10.rem == 2 then "2" else
        if d10.rem == 3 then "3" else
        if d10.rem == 4 then "4" else
        if d10.rem == 5 then "5" else
        if d10.rem == 6 then "6" else
        if d10.rem == 7 then "7" else
        if d10.rem == 8 then "8" else
        if d10.rem == 9 then "9" else
        abort null)
    );

  __mn_quotRem = x: y:
    let quot = x / y; in
    { inherit quot; rem = x - quot * y; };
  __mn_abs = x: if x < 0 then -x else x;

  __mn_attr_insertNew = as: x: e:
    if x == null then { } else
      assert !(as ? ${x}); as // __mn_singleton x e;
  __mn_attr_has_aux = d: e:
    if typeOf d != "set" then false else __mn_attr_has_prim d e;
  __mn_attr_has = e:
    __mn_matchList ({ head, tail, empty }:
      if empty then true else
      if __mn_attr_has_aux e head then __mn_attr_has e.${head} tail
      else false);
  __mn_attr_select = e:
    __mn_matchList ({ head, tail, empty }:
      if empty then e
      else __mn_attr_select e.${head} tail);
  __mn_attr_selectOr = e: as: d:
    if __mn_attr_has e as
    then __mn_attr_select e as
    else d;
  __mn_assert = e1: e2:
    if e1 then e2 else abort null;

  __mn_consAttrs = as: acc:
    __mn_foldr
      (x: acc: acc // {
        ${x} = [ as.${x} ] ++ (acc.${x} or [ ]);
      })
      acc
      (attrNames as);
  __mn_zipAttrs = __mn_foldr __mn_consAttrs { };

  # Old merge sort algorithm, taken from GHC.Internal.Data.OldList.
  __mn_mergesort = cmp: xs: __mn_mergesort' cmp (__mn_singletons xs);
  __mn_singletons = map (x: [ x ]);
  __mn_mergesort' = cmp: xs:
    __mn_matchList
      ({ head, tail, empty }:
        if empty then [ ] else if tail == [ ] then head else
        __mn_mergesort' cmp (__mn_mergePairs cmp xs))
      xs;
  __mn_mergePairs = cmp:
    __mn_matchList ({ head, tail, empty }: if empty then [ ] else
    let xs' = head; in __mn_matchList
      ({ head, tail, empty }:
        if empty then [ xs' ] else
        let ys' = head; xss' = tail; in
        [ (__mn_merge cmp xs' ys') ] ++ __mn_mergePairs cmp xss')
      tail);
  __mn_merge = cmp: xs: ys:
    __mn_matchList
      ({ head, tail, empty }:
        if empty then ys else
        let x = head; xs' = tail; in
        __mn_matchList
          ({ head, tail, empty }:
            if empty then xs else
            let y = head; ys' = tail; in
            if cmp y x
            then [ y ] ++ __mn_merge cmp xs ys' # y < x, i.e., x > y
            else [ x ] ++ __mn_merge cmp xs' ys)
          ys)
      xs;
}