(chapter-start 'list-manipulation "utilities for manipulating and iterating over lists, including filters and transforms")

(def zip args
  ; takes a list of lists, ((p q r) (1 2 3) (a b c) ...), returns ((p 1 a ...) (q 2 b ...) (r 3 c ...))
  (if (car args)
      (cons (map car args)
            (apply zip (map cdr args)))))

; invokes 'f for each element of 'things, first element processed first
; ( "l" in "eachl" = "leftmost first" )
(def eachl (f things)
  (loop (pair? things)
        (do
            (f (car things))
            (= things (cdr things)))))

;; if things is a pair,
;;   if (cdr things) is nil, return (car things)
;;   else recurse on (cdr things)
;; else return things
;;
;; 'it is used internally
;;
(def list/last (things it)
  (loop (pair? things)
        (= it     (car things)
           things (cdr things)))
  (or things it))

;; finds the index in 'things for which 'f returns non-nil,
;; or nil if not found
(def list/find-index (f things)
  (with (found nil
         i     -1)
    (loop (and things
               (no found))
     (= found  (f (car things))
        things (cdr things)
        i      (+ i 1)))
    (and found i)))

;; finds the index of 'thing in a list 'things, such that for example,
;; given a list 'my-list and an item 'thingy in the list,
;; (nth (list/index-of thingy my-list) my-list) will return the value of thingy.
;; returns nil if not found
(def list/index-of (thing things)
  (list/find-index
    (fn (it) (eq? it thing))
    things))

;; given a number 'n and a list 'things, return (a b) where a is
;; the item at index n-1 or nil if not possible, and b is the item
;; at index n+1 or nil if not possible
(def list/around (n things)
  (if (and n
           (< -1 n (len things)))
      (list
        (and (> n 0)
             (nth (- n 1) things))
        (nth (+ n 1) things))
      (list nil nil)))

;; finds the item before and the item after the given item in the  given list.
;; For example,
;; (list/around λx(eq? x 'd) '(a b c d e f) ) will return '(c e)
(def list/around-f (f things)
  (list/around
    (list/find-index f things)
    things))

;; finds the item before and the item after the given item in the  given list.
;; For example,
;; (list/around '(a b c d e f) 'd) will return '(c e)
(def list/around-thing (thing things)
  (list/around
    (list/index-of thing things)
    things))

; invokes 'f for each element of 'things, last element processed first
; ( "r" in "eachr" = "rightmost first" )
(def eachr (f things)
  (eachl f (rev things)))

; assign (cons x things) to things
(mac push (x things)
  `(= ,things (cons ,x ,things)))

;; used internally by 'flatmap
(def flatmap-helper (f things res)
  (loop (pair? things)
    (let a (car things)
      (= res
         (if (pair? a)
             (flatmap-helper f a res)
             a
             (cdr-set res (cons (f a)))
             res)
         things
         (cdr things))))
  (if things
      (= res (set-cdr res (f things))))
  res)

;; flatten the given list, transforming each leaf-item, recursively
(def flatmap (f things)
  (let res (cons)
    (flatmap-helper f things res)
    (cdr res)))

; flatten the given list, recursively
(def flatten (things) (flatmap x1 things))

; given a list 'al of form '( (k0 v0) (k1 v1) (k2 v2) ... (kn vn) ) and
; a 'key, returns the list (kx vx) from 'al where kx is equal to 'key
; #attribution: inspiration from arc.arc
(def assoc (key al)
  (if (pair? al)
      (if (caris key (car al))
          (car al)
          (assoc key (cdr al)))))

; given a list 'al of form '( (k0 v0) (k1 v1) (k2 v2) ... (kn vn) ) and
; a 'key, returns vx from 'al where kx is equal to 'key
; #attribution: lifted almost directly from arc.arc
(def alref (key al) (cadr (assoc key al)))