if cond (then) (else) = [[
  default-take [take :truthy cond] (:false else) then
]]

true = (:truthy :true)
false = (:truthy :false)

equal? a b = [default-take a (b true) false]

not v = [if v [give :truthy :false v] [give :truthy :true v]]

empty? map = [default-take map (() true) false]

zero = ()

succ num = [give :pred num ()]

pred num = [take :pred num]

add a b = [
  if [empty? a]
    b
    [succ [add [pred a] b]]
]

two = [succ [succ zero]]
four = [add two two]

identity a = a

const a = \_ -> a

. f g = \x -> [f [g x]]

nil = ()

cons value list = (:head value :tail list)

-- ++ : list a -> list a -> list a
++ as bs = [
  if [empty? as]
    bs
    [cons [:head as] [++ [:tail as] bs]]
]

-- concat : list (list a) -> list a
concat values = [
  if [empty? values]
    nil
    [++ [:head values] [concat [:tail values]]]
]

-- iterate-n : (a -> a) -> a -> nat -> list a
iterate-n f v n = [
  if [equal? n zero]
    nil
    [cons v [iterate-n f [f v] [pred n]]]
]

-- replicate : nat -> a -> list a
replicate n v = [
  if [equal? n zero]
    nil
    [cons v [replicate [pred n] v]]
]

-- intersperse : a -> list a -> list a
intersperse sep values =
  let
    prepend-all vs = [
      if [empty? vs]
        nil
        [cons sep [cons [:head vs] [prepend-all [:tail vs]]]]
    ]
  in [
    if [empty? values]
      nil
      [cons [:head values] [prepend-all [:tail values]]]
  ]

-- intercalate : list a -> list (list a) -> list a
intercalate sep vs = [concat [intersperse sep vs]]

-- fold : (a -> b -> b) -> b -> list a -> b
fold f init vs = [
  if [empty? vs]
    init
    [f [:head vs] [fold f init [:tail vs]]]
]

-- reverse : list a -> list a
reverse vs =
  let
    go vs acc = [
      if [empty? vs]
        acc
        [go [:tail vs] [cons [:head vs] acc]]
    ]
  in
    [go vs nil]

-- split: a -> list a -> list (list a)
split delim vs =
  let
    go vs acc = [
      if [empty? vs]
        [if [empty? acc] nil (|[reverse acc]|)]
        let
          first = [:head vs]
          rest = [:tail vs]
        in [
          if [equal? delim first]
            [cons [reverse acc] [go rest nil]]
            [go rest [cons first acc]]
        ]
    ]
  in
    [go vs nil]

apply fn v = [fn v]

assert c = [if c :pass :fail]

map f xs = [
  if [empty? xs]
    nil
    [cons [f [take :head xs]] [map f [take :tail xs]]]
]

filter p? xs = [
  if [empty? xs]
    nil
    let
      first = [take :head xs]
      rest = [take :tail xs]
    in [if [p? first]
         [cons first [filter p? rest]]
         [filter p? rest]]
]

silly-list = [cons :a [cons :b nil]]
silly-with-empties-list = [cons () [cons () [cons :a [cons () [cons :b [cons () nil]]]]]]

silly-fn v = [take v (:a :c :b :d)]

expected-map-list = [cons :c [cons :d nil]]
expected-filter-list = [cons :c [cons :d nil]]

always-true _ = true

cases = (|
  (:name :equal-for-keywords :assertion [equal? :foo :foo])
  (:name :equal-for-equal-maps :assertion [equal? two two])
  (:name :equal-for-non-equal-maps :assertion [not [equal? zero two]])
  (:name :equal-for-functions :assertion [equal? cons cons])
  (:name :cons-works :assertion [equal? [cons :foo nil] (:head :foo :tail ())])
  (:name :add-works-for-trivial-case :assertion [equal? [add zero two] two])
  (:name :add-works-for-harder-case :assertion [equal? [add two two] [succ [succ two]]])
  (:name :first-class-functions :assertion [equal? [apply identity :foo] :foo])
  (:name :map-for-trivial-case :assertion [equal? [map identity silly-list] silly-list])
  (:name :map-for-harder-case :assertion [equal? [map silly-fn silly-list] expected-map-list])
  (:name :filter-for-trivial-case :assertion [equal? [filter always-true silly-list] silly-list])
  (:name :filter-for-harder-case :assertion [equal? [filter [. not empty?] silly-with-empties-list] silly-list])
  (:name :compose-for-trivial-case :assertion [[. identity identity] true])
  (:name :compose-for-harder-case :assertion [[. not not] true])
  (:name :++-for-trivial-case :assertion [equal? [++ nil nil] nil])
  (:name :++-for-harder-case :assertion [equal? [++ (|:a :b :c|) (|:d :e|)] (|:a :b :c :d :e|)])
  (:name :concat-for-trivial-case :assertion [equal? [concat (| nil nil nil nil |)] nil])
  (:name :concat-for-harder-case :assertion [equal? [concat (| (|:a :b :c|) (|:d :e|) (|:f|) |)] (|:a :b :c :d :e :f|)])
  (:name :iterate-n-for-0 :assertion [equal? [iterate-n identity zero zero] nil])
  (:name :iterate-n-for-1 :assertion [equal? [iterate-n identity zero (:pred zero)] (|zero|)])
  (:name :iterate-n-for-n :assertion [equal? [iterate-n identity zero (:pred zero)] (|zero|)])
  (:name :iterate-n-for-n
    :assertion [equal?
      [iterate-n succ zero four]
      (|zero (:pred zero) two (:pred two)|)
    ]
  )
  (:name :replicate-for-n :assertion [equal? [replicate four four] (|four four four four|)])
  (:name :intersperse-for-empty :assertion [equal? [intersperse four nil] nil])
  (:name :intersperse-for-singleton :assertion [equal? [intersperse four (|four|)] (|four|)])
  (:name :intersperse-for-bigger-list
    :assertion [equal?
      [intersperse zero (|four four four|)]
      (|four zero four zero four|)
    ]
  )
  (:name :intercalate-for-empties
    :assertion [equal?
      [intercalate nil nil]
      nil
    ]
  )
  (:name :intercalate-for-non-trivial-case
    :assertion [equal?
      [intercalate ", " (|"hello" "world" "hi"|)]
      "hello, world, hi"
    ]
  )
  (:name :fold-for-empty-list
    :assertion [equal?
      [fold add four nil]
      four
    ]
  )
  (:name :fold-for-non-trivial-case
    :assertion [equal?
      [fold add zero (|two two four four|)]
      [add four [add four four]]
    ]
  )
  (:name :reverse-for-empty :assertion [empty? [reverse nil]])
  (:name :reverse-for-non-trivial-case
    :assertion [equal?
      [reverse (|zero two four|)]
      (|four two zero|)
    ]
  )
  (:name :split-for-empty :assertion [empty? [split ',' nil]])
  (:name :split-for-no-matches :assertion [equal? [split ',' "Hello"] (|"Hello"|)])
  (:name :split-for-simple-matches :assertion [equal? [split ',' "a,b,c"] (|"a" "b" "c"|)])
  (:name :split-for-match-on-the-end :assertion [equal? [split ',' "a,b,"] (|"a" "b"|)])
  (:name :split-for-consecutive-matches :assertion [equal? [split ',' "a,,b"] (|"a" "" "b"|)])
|)

taking key = \map -> [take key map]

assertion-fails case = [
  not [take :assertion case]
]

run-tests cases = [
  map [taking :name] [filter assertion-fails cases]
]

main = [run-tests cases]