#lang racket

(define head car)
(define tail cdr)

(define (begins-with? lst1 lst2)
  (cond [(null? lst1) #t]
        [(null? lst2) #f]
        [(not (equal? (head lst1) (head lst2))) #f]
        [else (begins-with? (tail lst1) (tail lst2))]))

(define (sublist? lst1 lst2)
  (cond [(null? lst2) (null? lst1)]
        [(begins-with? lst1 lst2) #t]
        [else (sublist? lst1 (tail lst2))]))

(define (filter p? list)
  (if (null? list) '()
      (if (p? (head list)) (cons (head list) (filter p? (tail list))) (filter p? (tail list)))))

(define (member? el list)
  (cond [(null? list) #f]
        [(equal? el (head list)) #t]
        [else (member? el (tail list))]))


(define (set-insert x lst)
  (if (member x lst)
      lst
      (cons x lst)))

(define (make-set lst)
  (foldr set-insert '() lst))

(define (length* lst)
  (foldr (lambda (el res) (+ res 1)) 0 lst))

(define (count-in-list el lst)
  (foldr (lambda (x count) (if (equal? el x) (+ 1 count) count)) 0 lst))

(define (histogram lst)
  (map (lambda (x) (cons x (count-in-list x lst))) (make-set lst)))

(define (quick-sort lst)
  (define (gen pred)
    (lambda (el) (pred el (head lst))))
  (if (or (null? lst)
          (null? (tail lst)))
      lst
      (append (quick-sort (filter (gen <) lst))
                          (filter (gen =) lst)
              (quick-sort (filter (gen >) lst)))))




(define (null-rows? m)  (null? m))
(define (null-cols? m)  (or (null? m) (null? (head m))))
(define (head-rows m)  (head m))
(define (head-cols m)  (map head m))
(define (tail-rows m)  (tail m))
(define (tail-cols m)  (map tail m))
(define (cons-rows row m) (cons row m))
(define (cons-cols col m) (map cons col m))
(define (transpose m)
  (if (null-cols? m)
      '()
      (cons-rows (head-cols m)
                 (transpose (tail-cols m)))))