fold-left and fold-right

9 files changed, 184 insertions, 18 deletions

diff --git a/coding-exercises/2/22.rkt b/coding-exercises/2/22.rkt
index 09ace8c..31f486a 100644
--- a/coding-exercises/2/22.rkt
+++ b/coding-exercises/2/22.rkt
@@ -13,24 +13,24 @@
             (cons (square (car things))
                   answer))))
   (iter items nil))
-;; (square-list (list 1 2 3 4))
+(square-list (list 1 2 3 4))
 
 ;; This attempts the reverse the consing direction by chaning the first in the pair with the second 
 ;; The result is that we get pairs that point to other pairs with car, which is not how a list works.
-(define (square-list2 items)
-  (define (iter things answer)
-    (if (null? things)
-      answer
-      (iter (cdr things)
-            (cons answer (square (car things))))))
-  (iter items nil))
-;;(square-list2 (list 1 2 3 4))
-
-;; One thing we could try is also growing the answer list forward somehow
-(define (square-list3 items)
-  (define (iter things answer)
-    (if (null? things)
-      answer
-      (iter (cdr things) (append answer (list (square (car things)))))))
-  (iter items (list)))
-(square-list3 (list 1 2 3 4))
+;; (define (square-list2 items)
+;;   (define (iter things answer)
+;;     (if (null? things)
+;;       answer
+;;       (iter (cdr things)
+;;             (cons answer (square (car things))))))
+;;   (iter items nil))
+;; ;;(square-list2 (list 1 2 3 4))
+;; 
+;; ;; One thing we could try is also growing the answer list forward somehow
+;; (define (square-list3 items)
+;;   (define (iter things answer)
+;;     (if (null? things)
+;;       answer
+;;       (iter (cdr things) (append answer (list (square (car things)))))))
+;;   (iter items (list)))
+;; (square-list3 (list 1 2 3 4))
diff --git a/coding-exercises/2/33.rkt b/coding-exercises/2/33.rkt
index cda82ce..85495eb 100644
--- a/coding-exercises/2/33.rkt
+++ b/coding-exercises/2/33.rkt
@@ -1,2 +1,23 @@
 #lang racket
+(require "../../shared/lists.rkt")
 
+(define (map p sequence)
+  (accumulate
+    (lambda (x y)
+      (cons (p x) y))
+    '() sequence))
+
+(define (append seq1 seq2)
+  (accumulate cons seq2 seq1))
+
+(define (length sequence)
+  (accumulate (lambda (x y)
+                (+ 1 y)) 0 sequence))
+
+(define test-seq (list 1 2 3 4 5 6 7 8 9 10))
+((lambda ()
+   (display (map (lambda (x) (* x x)) test-seq))
+   (newline)
+   (display (append test-seq test-seq))
+   (newline)
+   (display (length test-seq))))
diff --git a/coding-exercises/2/34.rkt b/coding-exercises/2/34.rkt
new file mode 100644
index 0000000..5850049
--- /dev/null
+++ b/coding-exercises/2/34.rkt
@@ -0,0 +1,10 @@
+#lang racket
+(require "../../shared/lists.rkt")
+
+(define (horner-eval x coefficient-sequence)
+  (accumulate (lambda (this-coeff higher-terms)
+                (+ this-coeff (* x higher-terms)))
+              0
+              coefficient-sequence))
+((lambda ()
+   (horner-eval 2 (list 1 3 0 5 0 1))))
diff --git a/coding-exercises/2/35.rkt b/coding-exercises/2/35.rkt
new file mode 100644
index 0000000..cc30571
--- /dev/null
+++ b/coding-exercises/2/35.rkt
@@ -0,0 +1,19 @@
+#lang racket
+(require "../../shared/lists.rkt")
+
+(define (count-leaves t)
+  (accumulate 
+    (lambda (x y) 
+      (+ x y)) 
+    0 
+    (map
+     (lambda (x) 
+       (if (pair? x)
+         (count-leaves x)
+         1)) t)))
+                      
+(define test-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)))
+((lambda ()
+   (display "testing")
+   (newline)
+   (display (count-leaves test-tree))))
diff --git a/coding-exercises/2/36.rkt b/coding-exercises/2/36.rkt
new file mode 100644
index 0000000..abe3feb
--- /dev/null
+++ b/coding-exercises/2/36.rkt
@@ -0,0 +1,13 @@
+#lang racket
+(require "../../shared/lists.rkt")
+
+(define (accumulate-n op init seqs)
+  (if (null? (car seqs))
+    '()
+    (cons (accumulate op init (map car seqs))
+          (accumulate-n op init (map cdr seqs)))))
+(define test-n (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
+((lambda ()
+   (display "testing")
+   (newline)
+   (display (accumulate-n + 0 test-n))))
diff --git a/coding-exercises/2/37.rkt b/coding-exercises/2/37.rkt
new file mode 100644
index 0000000..4acdc18
--- /dev/null
+++ b/coding-exercises/2/37.rkt
@@ -0,0 +1,34 @@
+#lang racket
+(require "../../shared/lists.rkt")
+
+(define (dot-product v w)
+  (accumulate + 0 (map * v w)))
+
+(define (matrix-*-vector m v)
+  (map (lambda (m-row)
+         (accumulate + 0 (map * m-row v))) m))
+
+(define (transpose mat)
+  (accumulate-n cons '() mat))
+
+(define (matrix-*-matrix m n)
+  (let ((cols (transpose n)))
+    (map (lambda (m-row)
+           (map (lambda (n-col)
+                  (dot-product m-row n-col)) cols)) m)))
+
+(define test-m (list (list 1 2 3 4)
+                     (list 4 5 6 6)
+                     (list 6 7 8 9)))
+(define test-n (list (list 1 2 3)
+                     (list 4 5 6)
+                     (list 6 7 8)
+                     (list 6 7 8)))
+(define test-v (list 1 2 3 4))
+((lambda ()
+   (newline)
+   (display (matrix-*-vector test-m test-v))
+   (newline)
+   (display (transpose test-m))
+   (newline)
+   (display (matrix-*-matrix test-m test-n))))
diff --git a/coding-exercises/2/38.rkt b/coding-exercises/2/38.rkt
new file mode 100644
index 0000000..456e283
--- /dev/null
+++ b/coding-exercises/2/38.rkt
@@ -0,0 +1,24 @@
+#lang racket
+(require "../../shared/lists.rkt")
+
+(define (fold-right op initial sequence)
+  (accumulate op initial sequence))
+
+(define (fold-left op initial sequence)
+  (define (iter result rest)
+    (if (null? rest)
+      result
+      (iter (op result (car rest))
+            (cdr rest))))
+  (iter initial sequence))
+
+((lambda ()
+   (newline)
+   (display (fold-right / 1 (list 1 2 3)))
+   (newline)
+   (display (fold-left / 1 (list 1 2 3)))
+   (newline)
+   (display (fold-right list '() (list 1 2 3)))
+   (newline)
+   (display (fold-left list '() (list 1 2 3)))))
+   
diff --git a/coding-exercises/2/39.rkt b/coding-exercises/2/39.rkt
new file mode 100644
index 0000000..2d80dde
--- /dev/null
+++ b/coding-exercises/2/39.rkt
@@ -0,0 +1,19 @@
+#lang racket
+(require "../../shared/lists.rkt")
+
+(define (reverse-r sequence)
+  (fold-right (lambda (x y)
+                (append y (list x)))
+              '()
+              sequence))
+
+(define (reverse-l sequence)
+  (fold-left (lambda (y x) 
+               (cons x y))
+             '() 
+             sequence))
+
+(define test-list (list 1 2 3))
+((lambda ()
+   (display (reverse-r test-list))
+   (display (reverse-l test-list))))
diff --git a/shared/lists.rkt b/shared/lists.rkt
index d5cfc61..4f2184d 100644
--- a/shared/lists.rkt
+++ b/shared/lists.rkt
@@ -1,4 +1,8 @@
 #lang racket
+(provide accumulate
+         accumulate-n
+         fold-right
+         fold-left)
 (define (append list1 list2)
   (if (null? list1)
     list2
@@ -22,3 +26,25 @@
   (if (null? (cdr l))
     l
     (last-pair (cdr l))))
+
+(define (accumulate op initial sequence)
+  (cond ((null? sequence) initial)
+        (else (op (car sequence)
+                  (accumulate op initial (cdr sequence))))))
+
+(define (accumulate-n op init seqs)
+  (if (null? (car seqs))
+    '()
+    (cons (accumulate op init (map car seqs))
+          (accumulate-n op init (map cdr seqs)))))
+
+(define (fold-right op initial sequence)
+  (accumulate op initial sequence))
+
+(define (fold-left op initial sequence)
+  (define (iter result rest)
+    (if (null? rest)
+      result
+      (iter (op result (car rest))
+            (cdr rest))))
+  (iter initial sequence))