#lang lazy
(provide permute
         unique
         take drop
         init last
         take-while drop-while
         span break
         group-by
         any
         all
         words 
         
         digits from-digits
         digit?
         char->digit 
         digit->char
         
         combine)

; Given a list of items 
; generate a list of all possible permutations of the list
; including duplicates 
(define (permute l)
  (cond [(null? l) null]
        [(null? (rest l)) (list l)]
        ;; append-map => (apply append map ...
        [else (apply append map  
               (λ (head)
                 (map 
                  (λ (tail) 
                    (cons head tail))
                  (permute (remove head l))))
               l)]))

; Remove duplicates from xs
(define (unique xs)
  (cond [(null? xs) null]
        [else (let ([head (first xs)]
                    [tail (rest xs)])
                (cons head (unique (remove* (list head) tail))))]))

; Return the first n items from the head of xs
(define (take n xs)
  (cond [(or (<= n 0)
             (null? xs)) null]
        [else (cons (first xs)
                    (take (sub1 n) (rest xs)))]))

; Remove the first n items from the head of xs
(define (drop n xs)
  (cond [(or (<= n 0)
             (null? xs)) xs]
        [else (drop (sub1 n) (rest xs))]))

; Return all but the final item of the list
(define (init xs) (reverse (rest (reverse xs))))


; Remove the final item of the list
(define (last xs) (first (reverse xs)))

; Return list items while the predicate is true
(define (take-while p xs)
  (cond [(null? xs)     null]
        [(p (first xs)) (cons (first xs) (take-while p (rest xs)))]
        [else           null]))

; Drop list items while the predicate is true
(define (drop-while p xs)
  (cond [(null? xs)     null]
        [(p (first xs)) (drop-while p (rest xs))]
        [else           xs]))

; Return values (ts, rs)
; ts are all the items from the beginning iof the list where the predicate is true
; rs is the remainder of the list
(define (span p xs)
  (let loop ([trues null]
             [untested xs])
    (cond [(null? untested)     (values (reverse trues) untested)]
          [(p (first untested)) (loop (cons (first untested) trues) (rest untested))]
          [else                 (values (reverse trues) untested)])))
; Return values (fs, rs)
; fs are all the items from the beginning iof the list where the predicate is false
; rs is the remainder of the list
(define (break p xs)
  (let loop ([falses null]
             [untested xs])
    (cond [(null? untested)     (values (reverse falses) untested)]
          [(p (first untested)) (values (reverse falses) untested)]
          [else                 (loop (cons (first untested) falses) (rest untested))])))

; (a -> a-> boolean) -> (a) -> ((a))
;groupBy _  []           =  []
;groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
;                           where (ys,zs) = span (eq x) xs
(define (group-by pred? xs)
  (cond [(null? xs) null]
        [else (let*-values ([(x)     (first xs)]
                            [(xs)    (rest xs)]
                            [(ys zs) (span (λ (z) (pred? x z)) xs)])
                (cons (cons x ys)
                      (group-by pred? zs)))]))

(define any ormap)
(define all andmap)

;words s =  
;  case dropWhile isSpace s of
;    "" -> []
;    s' -> w : words s''
;    where (w, s'') = break isSpace s'
(define (words s)
  (let ws ([s (string->list s)])
    (let*-values ([(next-word) (drop-while char-whitespace? s)] 
                  [(w s+) (break char-whitespace? next-word)])
      (if (null? next-word) 
          null
          (cons (list->string w) (ws s+))))))

;unwords []              =  ""
;unwords [w]             = w
;unwords (w:ws)          = w ++ ' ' : unwords ws
(define (unwords ws)
  (cond [(null? ws) null]
        [(null? (rest ws)) (first ws)]
        [else (string-append (string-append (first ws) " ")
                             (unwords (rest ws)))]))


; integer code for the character 0
(define *zero-char-code* (char->integer #\0))

; char -> boolean
(define (digit? c)
  (and (char>=? c #\0)
       (char<=? c #\9)))

; char -> integer
; convert char representing a digit to the digit value
(define (char->digit c)  
  (if (digit? c)
      (- (char->integer c) *zero-char-code*)
      (error "char->digit expects a character representing a digit : " c)))

; integer -> char
; convert a digit to the char representing it
(define (digit->char d) 
  (if (and (>= d 0)
           (< d 10))
      (integer->char (+ *zero-char-code* d))
      (error "char->digit expects a character representing a digit : " d)))

; integer -> (char)
; a list of the digits of n
(define (digits n)       (map char->digit (string->list (number->string n))))

; (char) -> integer
; the number n given a list of its digits
(define (from-digits ds) (string->number (list->string  (map digit->char ds))))

; (b->c) -> (a->b) -> (a->c)
; compose f and g 
(define (combine f g) (λ (n) (f (g n))))