#lang typed/scheme
(provide (all-defined-out))

;;=================================================================
;; List Utilities

;; Remove the first element satisfying f (if any).
(: remf (All (X) ((X -> Boolean) [Listof X] -> [Listof X])))
(define (remf f ls)
  (cond [(empty? ls) empty]
        [(f (first ls)) (rest ls)]
        [else 
         (cons (first ls)
               (remf f (rest ls)))]))

;; Interleave x between each pair of elements in ys.
(: interleave (All (X) (X [Listof X] -> [Listof X])))
(define (interleave x ys)
  (cond [(empty? ys) ys]
        [(empty? (rest ys)) (list (first ys))]
        [else
         (cons (first ys)
               (cons x
                     (interleave x (rest ys))))]))

(: replace-at (All (X) ([Listof X] X Exact-Nonnegative-Integer -> [Listof X])))
(define (replace-at ls x i)
  (append (take ls i)
          (list x)
          (drop ls (add1 i))))

(: remove-at (All (X) ([Listof X] Exact-Nonnegative-Integer -> [Listof X])))
(define (remove-at ls i)
  (append (take ls i)
          (drop ls (add1 i))))

;; Given a non-empty list, returns a list of all but the
;; last element.
(: all-but-last (All (X) ((Pair X (Listof X)) -> (Listof X))))
(define (all-but-last segs)
  (let ((r (rest segs))) ; important for type checking.
    (cond [(empty? r) empty]
          [else (cons (first segs) (all-but-last r))])))