;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname 2015-10-26-lerner) (read-case-sensitive #t) (teachpacks ((lib "image.rkt" "teachpack" "2htdp") (lib "universe.rkt" "teachpack" "2htdp") (lib "batch-io.rkt" "teachpack" "2htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "image.rkt" "teachpack" "2htdp") (lib "universe.rkt" "teachpack" "2htdp") (lib "batch-io.rkt" "teachpack" "2htdp")) #f)))
;; turns (list a b c) into (list (f a) (f b) (f c)), etc.
;; map : [X -> Y] [Listof X] -> [Listof Y]
(define (my-map f alist)
  (cond
    [(empty? alist) empty]
    [(cons? alist)
     (cons (f (first alist))
           (my-map f (rest alist)))]))

;; turns (cons a (cons b (cons c empty))) into
;;       (op   a (op   b (op   c base)))
;; foldr : [X Y -> Y] Y [Listof X] -> Y
(define (my-foldr op base alist)
  (cond
    [(empty? alist) base]
    [(cons? alist)
     (op (first alist)
         (my-foldr op base (rest alist)))]))

;; map-via-fold : [X -> Y] [Listof X] -> [Listof Y]
(define (map-via-fold.v1 f alist)
  (local ((define (op first-alist map-f-rest)
            (cons (f first-alist) map-f-rest)))
    (foldr op
           empty
           alist)))
;====== equivalent to =====
(define (map-via-fold f alist)
  (foldr (λ(first-alist map-f-rest)
           (cons (f first-alist) map-f-rest))
         empty
         alist))
#|

(map f (list a b c))
==defined to be==
(foldr op empty (list a b c))
==in one expansion==
(op a       (foldr op empty (list b c)))
===assuming foldr does what we want, via recursion===>
(op a       (cons (f b) (cons (f c) empty)))
???
(cons (f a) (cons (f b) (cons (f c) empty)))
|#


  


;; returns the list of items for which pred returns true
(define (my-filter pred alist)
  (cond
    [(empty? alist) empty]
    [(cons? alist)
     (if (pred (first alist))
         (cons (first alist) (my-filter pred (rest alist)))
         (my-filter pred (rest alist)))]))

(define (filter-via-fold pred alist)
  (foldr (λ(first-alist filtered-rest-alist)
           (if (pred first-alist)
               (cons first-alist filtered-rest-alist)
               filtered-rest-alist))
         empty
         alist))





;; and-map : [X -> Boolean] [Listof X] -> Boolean
;; returns true if the predicate is true for every item in the list
(define (and-map pred alist)
  (cond
    [(empty? alist) true]
    [(cons? alist)
     (and (pred (first alist))
          (and-map pred (rest alist)))]))
(define (and-map-via-fold pred alist)
  (foldr (λ(x y) (and x y)) true (map pred alist)))



;; or-map : [X -> Boolean] [Listof X] -> Boolean
;; returns true if the predicate is true for any item in the list
(define (or-map pred alist)
  (cond
    [(empty? alist) false]
    [(cons? alist)
     (or (pred (first alist))
         (or-map pred (rest alist)))]))
(define (or-map-via-fold pred alist)
  (foldr (λ(x y) (or x y)) false (map pred alist)))

;; build-list : Number [Number -> Y] -> [Listof Y]
;; (build-list n f) returns (list (f 0) (f 1) (f 2) ... (f (sub1 n)))

;; make-list : Number X -> [Listof X]
;; (make-list n x) returns (list x x x ... x) of length n




;; flatten : [Listof [Listof X]] -> [Listof X]
(define (my-flatten.v1 xss)
  (cond
    [(empty? xss) empty]
    [(cons? xss)
     (my-append (first xss) (my-flatten.v1 (rest xss)))]))
(define (my-flatten xss)
  (foldr my-append empty xss))

;; append : [Listof X] [Listof X] -> [Listof X]
(define (my-append.v1 list1 list2)
  (cond
    [(empty? list1) list2]
    [(cons? list1)
     (cons (first list1)
           (my-append.v1 (rest list1) list2))]))
(define (my-append list1 list2)
  (foldr cons list2 list1))