#lang racket
(require racket/trace)

; (product '(a b c) '(x y)) - > '((a x) (a y) (b x) (b y) (c x) (c y))

(define p1
  (lambda (l1 l2)
    (map list l2)))

(define p2
  (lambda (l1 l2)
    (map (lambda (x) (list (car l1) x)) l2)))

(define p3
  (lambda (l1 l2)
    (map (lambda (x) (map (lambda (y) (list x y)) l2)) l1)))

(define p4
  (lambda (l1 l2)
    (apply append (map (lambda (x) (map (lambda (y) (list x y)) l2)) l1))))

; (qsort <= '(4 2 4 3 2 4 1 8 2 1 3 4)) -> '(1 1 2 2 2 3 3 4 4 4 4 8)

;(qsort (lambda (x y) (<= (abs (- x 10)) (abs (- y 10)))) '(5 1 10 8 16 17 23 -1))
;  -> (10 8 5 16 17 1 -1 23)

(define q1
  (lambda (ls)
    (if (null? ls) '()
        (if (null? (cdr ls)) ls
            (let ([pivot (car ls)])
              (let ([lower (filter (lambda (x) (< x pivot)) (cdr ls))]
                     [upper (filter (lambda (x) (>= x pivot)) (cdr ls))])
                (append
                 (q1 lower)
                 (list pivot)
                 (q1 upper))))))))

(define q2
  (lambda (proc ls)
    (if (null? ls) '()
        (if (null? (cdr ls)) ls
            (let ([pivot (car ls)])
              (let ([lower (filter (lambda (x) (proc x pivot)) (cdr ls))]
                     [upper (filter (lambda (x) (not (proc x pivot))) (cdr ls))])
                (append
                 (q2 proc lower)
                 (list pivot)
                 (q2 proc upper))))))))

(define q3
  (lambda (proc ls)
    (if (null? ls) '()
        (if (null? (cdr ls)) ls
            (let ([pivot (car ls)])
              (let ([lower (filter (lambda (x) (proc x pivot)) (cdr ls))]
                     [upper (filter-not (lambda (x) (proc x pivot)) (cdr ls))])
                (append
                 (q3 proc lower)
                 (list pivot)
                 (q3 proc upper))))))))

; The following is an efficiency improvement
(define q4
  (lambda (proc ls)
    (if (null? ls) '()
        (if (null? (cdr ls)) ls
            (let* ([pivot (car ls)]
                   [procp (lambda (x) (proc x pivot))])
              (let ([lower-upper (helper procp (cdr ls) '() '())])
                (append
                 (q4 proc (car lower-upper))
                 (list pivot)
                 (q4 proc (cadr lower-upper)))))))))

(define helper
  (lambda (procp ls lower upper)
    (if (null? ls)
        (list lower upper)
        (if (procp (car ls))
            (helper procp (cdr ls) (cons (car ls) lower) upper)
            (helper procp (cdr ls) lower (cons (car ls) upper))))))

(define q42
  (lambda (proc ls)
    (if (null? ls) '()
        (if (null? (cdr ls)) ls
            (let* ([pivot (car ls)]
                   [procp (lambda (x) (proc x pivot))])
              (letrec ([helper (lambda (ls lower upper)
                                 (if (null? ls) (list lower upper)
                                     (if (procp (car ls))
                                          (helper (cdr ls) (cons (car ls) lower) upper)
                                          (helper (cdr ls) lower (cons (car ls) upper)))))])
                (let ([lower-upper (helper (cdr ls) '() '())])
                  (append (q42 proc (car lower-upper))
                          (list pivot)
                          (q42 proc (cadr lower-upper))))))))))

(define atom?
  (lambda (x)
    (and (not (pair? x))
         (not (null? x)))))

; A more appropriate test for whether the car of ls is a list. Using the racket procedure "list?" is
; too expensive, because it is linear. Please use this procedure.

(define snlist-recur
  (lambda (flist fatom init)
    (letrec ([helper (lambda (l)
		       (cond [(null? l) init]
			     [(or (pair? (car l))
                                  (null? (car l))) (flist (helper (car l))
						     (helper (cdr l)))]
			     [else (fatom (car l) (helper (cdr l)))]))])
      helper)))


;(define reverse (snlist-recur (lambda (x y) )   (lambda (x y) )  '()))

; Returning a procedure which has access to a variable defined by a let
(define make-counter
  (lambda ()
    (let ([num 0])
      (lambda ()
        (set! num (add1 num))
        num))))


(define member?
  (lambda (item ls)
    ((member?-c item) ls)))

; Returning a procedure that has access to the parameter passed to it.
(define member?-c
  (lambda (item)
    (letrec ([helper (lambda (ls)
                     (if (null? ls) #f
                         (or (eq? (car ls) item)
                             (helper (cdr ls)))))])
      helper)))