#lang racket

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(define (square x) (* x x))

;; 2.30 oooh, we getting cool now are we?
(define (square-tree l)
  (cond
    ((null? l) l)
    ((list? (car l)) (cons (square-tree (car l))
                           (square-tree (cdr l))))
    (#t (cons (square (car l))
              (square-tree (cdr l))))))

(define (square-tree-map l)
  (map (λ (x)
         (if (list? x)
             (square-tree-map x)
             (square x)))
       l))

;; 2.31 hohoohoho nice
(define (tree-map f l)
  (map (λ (x)
         (if (list? x)
             (tree-map f x)
             (f x)))
       l))
(define (square-tree-final l) (tree-map square l))

;; 2.32 hmm.. cool stuff.
(define (subsets s)
  (if (null? s)
      (list '())
      (let ((rest (subsets (cdr s))))
        (append rest (map (λ (l) (cons (car s) l)) rest)))))
;; The reason this works, is because the set of subsets of a set s
;; can be defined as such:
;;  - if s is the empty set, the result is a set containing the empty set
;;  - otherwise, the result is a set containing:
;;    1. the subsets of s without the first element of s
;;    2. the subsets of s with the first element of s
;;    2 can be defined as the first element of s added to every
;;    subset of s that does not contain the first element of s.
;; probably not a very rigorous or formal definition, but good
;; enough for now.


;; 2.33
;; this one kinda tripped me up for a long while, because
;; I'm used to using `reduce` for this kind of stuff (yeah
;; I used to do common lisp) and accumulate here is basically
;; reduce, but kind of wonky.
;; e.g. (reduce (λ (x y) ...) seq) is (kind of, not really) equivalent to
;;      (accumulate (λ (x y) ...) (car seq) (cdr seq))
;; not exactly equivalent, the order in which accumulate traverses
;; its list argument is also the reverse of reduce... but you get the idea.
;;
;; edit after 2.38: apparently racket also has both accumulate and reduce:
;; they're called foldr and foldl respectively. (though still a little different,
;; compared to reduce, the differences are mostly trivial)
(define (my-map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) '() sequence))
(define (my-append seq1 seq2)
  (accumulate cons seq2 seq1))
(define (my-length sequence)
  (accumulate (λ (x y) (+ y 1)) 0 sequence))

;; 2.34
;; first element of coefficient-sequence is the coefficient of x^0, then x^1 and so on.
(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ (* higher-terms x) this-coeff))
              0
              coefficient-sequence))

;; 2.35
(define (count-leaves t)
  (accumulate + 0
              (map (λ (x) (if (cons? x)
                              (count-leaves x)
                              1))
                   t)))

;; 2.36
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

;; 2.37 yeah, I'm not good with matrix stuff.
(define (dot-product v w)
  (accumulate + 0 (map * v w)))
(define (matrix-*-vector m v)
  (map (λ (x) (dot-product x v)) m))
(define (transpose mat)
  (accumulate-n cons '() mat))
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (λ (v) (matrix-*-vector cols v)) m)))
;; not sure about matrix-*-matrix, I didn't bother to check
;; if it was correct


;; 2.38 (op a b) must strictly equal (op b a)
;; a.k.a the operation must be commutative.

;; 2.39
(define (reversel sequence)
  (foldl (lambda (x y) (cons x y)) '() sequence))
(define (reverser sequence)
  (foldr (lambda (x y) (append y (list x))) '() sequence))
;; reverser is kinda inefficient, has to traverse y for each x
;; has O(N^2) time complexity as a result and so I hate it.
;; compare it to reversel which is O(N)