An illustration of rewrite rules for the lambda calculus

And this is a possible implementation of the split() function:

    def split(l: List(f24)) -> (List(f24), List(f24)):
      return split_inner(l, List/Nil, List/Nil)

    def split_inner(l: List(f24), a: List(f24), b: List(f24)) -> (List(f24), List(f24)):
      match l:
        case List/Nil:
          return (a, b)
        case List/Cons:
          return split_inner(l.tail, List/Cons(l.head, b), a)


    def merge_lists(a: List(f24), b: List(f24)) -> List(f24):
      match a:
        case List/Nil:
          return b
        case List/Cons:
          match b:
            case List/Nil:
              return a
            case List/Cons:
              if a.head < b.head:
                return List/Cons(a.head, merge_lists(a.tail, b))
              else:
                return List/Cons(b.head, merge_lists(b.tail, a))