lib.lal

(defun 'map 'fn 'ls
  (letrec
    '_map (lambda 'fn 'first 'rest
            (let 'result (fn first)
              (if rest
                (extend
                  (list result)
                  (_map fn (head rest) (tail rest))
                )
                (list result)
              )
            )
          )
    (if ls
      (extend
        (list)
        (_map fn (head ls) (tail ls))
      )
      ls
    )
  )
)

(defun 'enumerate 'ls
  (if ls
    (letrec
      '_enumerate
        (lambda 'first 'rest 'idx
          (let 'res (list first idx)
            (if rest
              (extend (list res)
                      (_enumerate
                        (head rest)
                        (tail rest)
                        (+ idx 1)
                      )
              )
              (list res)
            )
          )
        )
      (_enumerate (head ls) (tail ls) 0)
    )
    ls
  )
)

# Return a list of pairs of items from each list
# [[item 1 from list 1, item 1 from list 2], ...]
# Stops as soon as one of the lists runs out
(defun 'zip 'l1 'l2
  (if (and l1 l2)
    (letrec '_zip
      (lambda 'first_l1 'rest_l1 'first_l2 'rest_l2
        (let 'pair (list first_l1 first_l2)
          (if rest_l1
            (if rest_l2
              (extend (list pair) (_zip (head rest_l1) (tail rest_l1) (head rest_l2) (tail rest_l2)))
              (list pair)
            )
            (list pair)
          )
        )
      )
      (_zip (head l1) (tail l1) (head l2) (tail l2))
    )
    (list)
  )
)

# Like zip but if one list runs out before the other
# we insert the value fill. Until both lists are exhausted.
(defun 'ziplongest 'l1 'l2 'fill
  (if (or l1 l2)
    (letrec '_ziplongest
      (lambda 'l1 'l2
        (if (and (empty l1) (empty l2))
          # Reached end of both lists, exit
          (list)
          # Otherwise keep pairing
          (extend (list
                    (list
                      # First item if we've got it, otherwise fill
                      (if l1 (head l1) fill)
                      (if l2 (head l2) fill)
                    )
                  )
                  (_ziplongest
                    (if l1 (tail l1) l1)
                    (if l2 (tail l2) l2)
                  )
          )
        )
      )
      (_ziplongest l1 l2)
    )
    # Both empty, no pairs to make
    (list)
  )
)

(defun 'contains 'target 'ls
  (neq
    (findif (lambda 'x (eq target x)) ls)
    (none)
  )
)

(defun 'findif 'fn 'ls
  (letrec
    '_findif (lambda 'fn 'first 'rest
            (if (fn first)
              first
              (if rest
                (_findif fn (head rest) (tail rest))
                (none)
              )
            )
          )
    (if ls
      (_findif fn (head ls) (tail ls))
      (none)
    )
  )
)

(defun 'apply 'fn 'ls
  (letrec
    '_apply (lambda 'fn 'first 'rest
              (body
                (fn first)
                (if rest
                  (_apply fn (head rest) (tail rest))
                )
              )
            )
    (if ls
      (_apply fn (head ls) (tail ls))
      (none)
    )
  )
)

(defun 'filter 'fn 'ls
  (letrec
    '_filter (lambda 'fn 'first 'rest
            (let 'result (if (fn first)
                           (list first)
                           (list)
                         )
              (if rest
                (extend
                  result
                  (_filter fn (head rest) (tail rest))
                )
                result
              )
            )
          )
    (if ls
      (extend
        (list)
        (_filter fn (head ls) (tail ls))
      )
      ls
    )
  )
)

(defun 'accumulate 'fn 'ls 'initial
  (letrec '_accumulate
    (lambda 'fn 'total 'first 'rest
      (if rest
        (_accumulate fn
          (fn total first)
          (head rest)
          (tail rest)
        )
        (fn total first)
      )
    )
    (if ls
      (_accumulate fn initial (head ls) (tail ls))
      initial
    )
  )
)

(defun 'index 'target 'ls
  (letrec '_index
    (lambda 'first 'rest 'idx
      (if (eq target first)
        idx
        (if rest
          (_index (head rest) (tail rest) (+ idx 1))
          (none)
        )
      )
    )
    (if ls
      (_index (head ls) (tail ls) 0)
      (none)
    )
  )
)

# Remove the first item matching target
(defun 'remove 'target 'ls
  (if ls
    (letrec
      '_remove
        (lambda 'first 'rest
          # If we found the thing to remove
          (if (eq target first)
            # Return the rest, dropping the target item
            rest
            # Else continue searching for it while there are items
            (extend
              (list first)
              (if rest
                (_remove
                  (head rest)
                  (tail rest)
                )
                (list)
              )
            )
          )
        )
     (_remove (head ls) (tail ls))
    )
    # For empty list just return it
    ls
  )
)

# TODO: this could also be done as a builtin
(defun 'nth 'idx 'ls
  (letrec '_nth
    (lambda 'rest 'curr_idx
      (if (eq curr_idx idx)
        (head rest)
        (_nth (tail rest) (+ curr_idx 1))
      )
    )
    (if (eq idx 0)
      (head ls)
      (_nth (tail ls) 1)
    )
  )
)

(defun 'empty 'ls
  (eq 0 (len ls))
)

(defun 'max 'ls
  (letrec '_max
    (lambda 'current_max 'first 'rest
      (let 'new_max
             (if (> first current_max)
                first
                current_max
             )
        (if rest
          (_max new_max (head rest) (tail rest))
          new_max
        )
      )
    )
    (_max (head ls) (head ls) (tail ls))
  )
)

# Note that split is implemented in terms of split_once
# to reduce the number of recursive calls we make.
(defun 'split 'str 'char
  (letrec
    '_split
      (lambda 'str
        (letrec 'once       (split_once str char)
                'split_part (nth 0 once)
                'remaining  (nth 1 once)
          # If this split call consumed all the remaining chars...
          #
          # The reason we don't just say (if remaining) is
          # that if you split "foo?" by "?" once you get ["foo" ""].
          # If we stop there you would get result ["foo"] when we actually
          # want ["foo" ""].
          # So instead we check that the returned part has the same length
          # as the remainder. In this example, that
          # (len "foo") == (len "foo?") which is false so we split
          # again. We get ["" ""] so (len "") == (len "") and we can
          # know we've consumed the whole input string.
          # So the final result is ["foo" ""] as expected.
          (if (eq (len split_part) (len str))
            # Return the result of the split
            (list split_part)
            # Otherwise split again on the remaining chars
            (extend (list (nth 0 once)) (_split (nth 1 once)))
          )
        )
      )
    (_split str)
  )
)

# Mainly here to implement split but might be useful for something else
# Returns the split part of the string, and any unused chars
# E.g (split_once "foo?bar" "?") => ["foo" "bar"]
(defun 'split_once 'str 'char
  (letrec
    '_split_once
      (lambda 'str 'acc
        (if str
          (let 'first (head str) 'rest (tail str)
            (if (eq first char)
              # We return rest here so that we consume the split char
              (list acc rest)
              (_split_once rest (+ acc first))
            )
          )
          (list acc str)
        )
      )
    (_split_once str "")
  )
)

(defun 'reverse 'ls
  (if (> (len ls) 1)
    (letrec
      '_reverse
        (lambda 'first 'rest
          (if rest
            (extend (_reverse (head rest) (tail rest)) (list first))
            (list first)
          )
        )
      (_reverse (head ls) (tail ls))
    )
    ls
  )
)

(defun 'range 'min 'max
  (if (< min max)
    (letrec
      '_range (lambda 'n
        (if (eq n max)
          (list)
          (extend (list n) (_range (+ n 1)))
        )
      )
      (_range 0)
    )
    # TODO: error here?
    (list)
  )
)