Here is exercise 2.6 from SICP: Exercise 2.6: In case representing pairs as procedures wasn’t mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as ``` (define zero (lambda (f) (lambda (x) x))) (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x))))) ``` This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the λ-calculus. Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1). Please review my code: ``` (define one (lambda (f) (lambda (x) (f x)))) (define two (lambda (f) (lambda (x) (f (f x))))) ;; I used an identity function to check the + procedure (define (+ a b) (lambda (f) (lambda (x) ((((a f) b) f) x)))) ``` How can I improve this code?

Define a procedure that takes three numbers as arguments and returns the sum of squares of the two largest numbers. I'm using just the machinery that was developed so far in SICP to be true to the exercise. My method works as far as I can tell -- I tested it for a number of cases and tested different permutations of inputs and get the same answers in each case. I just wasn't sure if there were a better way to do this exercise. Any feedback whatsoever is welcomed. ``` ;; Define the squaring function. (define (square n) (* n n) ) ;; Define the maximum of two inputs a and b. (define (mx a b) (cond ((< a b) b) ((< b a) a) ((= a b) a)) ) ;; Define the constant of elimination. (define (coe x y z) (cond ((= x y) (-(square x))) ((= y z) (-(square y))) ((= x z) (-(square z)))) ) ;; Define the sum of squares function. It consists of the sum of squares of the maxima of ;; each of three possible pairs of three elements. Two of the first three terms will always ;; evaluate to the same value, and so the constant of elimination is added to get rid of the redundant term. (define (sosl a b c) (+ (square (mx a b)) (square (mx b c)) (square (mx a c)) (coe (mx a b) (mx b c) (mx a c)) ) ) ```

From SICP: Exercise 1.12: The following pattern of numbers is called Pascal’s triangle. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 . . . The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal’s triangle by means of a recursive process. Here is my code: ``` (define (pascals-triangle row col) ;; "The numbers at the edge of the triangle are all 1" (if (or (= col 0) (= col row)) 1 (+ (pascals-triangle (- row 1) (- col 1)) (pascals-triangle (- row 1) col)))) ``` I noticed that the edges of the triangle after 1 is (probably) always the number of rows, because we always add 1 to them when we go to the next row. So I rewrote the code with a minor change. ``` (define (pascals-triangle row col) (cond ((or (= col 0) (= col row)) 1) ((or (= col 1) (= col (- row 1))) row) (else (+ (pascals-triangle (- row 1) (- col 1)) (pascals-triangle (- row 1) col))))) ``` In my previous code, if the colum is 0, the running time is constant. Now in the revised code, it's also constant if the column is 1. And since this is recursive, I am guessing I saved a few steps. Will making small changes like that have a significant impact with my code and systems a lot larger than this? How can I improve this code?

I have done exercise 1.7 in SICP (calculate square root precision when change in guesses is under a certain value), but I am calling the change-in-precision function twice in each iteration, which disturbs me. I wonder if there is a better way to implement this. ``` (define (average . ns) (/ (apply + ns) (length ns))) (define (change-in-precision guess x) ( - (- guess (average guess (/ x guess))))) (define (sqrt guess x) (if (< (abs (change-in-precision guess x)) (/ 0.00000001 guess)) (+ guess (change-in-precision guess x)) (sqrt (+ guess (change-in-precision guess x)) x))) ```

From SICP Exercise 2.69: The following procedure takes as its argument a list of symbol-frequency pairs (where no symbol appears in more than one pair) and generates a Huffman encoding tree according to the Huffman algorithm. ``` (define (generate-huffman-tree pairs) (successive-merge (make-leaf-set pairs))) ``` Make-leaf-set is the procedure given above that transforms the list of pairs into an ordered set of leaves. Successive-merge is the procedure you must write, using make-code-tree to successively merge the smallest-weight elements of the set until there is only one element left, which is the desired Huffman tree. (This procedure is slightly tricky, but not really complicated. If you find yourself designing a complex procedure, then you are almost certainly doing something wrong. You can take significant advantage of the fact that we are using an ordered set representation.) - make-code-tree creates a tree from two branches, make those branches as left and right branches respectively, combine all symbols of the branches as its own set of symbols, and finally add the weights of the branches as its own weight. - adjoin-set inserts a tree to the set while remaining ordered based on the weight of the items. Though I am confident my code is correct, I am extremely unsure of my solution. What's bothering me is the hint that it's tricky. It does gave correct results for all tests I did. I have thought of alternative ways of doing this, but the procedures I came up with were very complex. Also, I think this is very slow. Please review my code. ``` (define (successive-merge leaves) (if (= (length leaves) 1) (car leaves) (successive-merge (adjoin-set (make-code-tree (car leaves) (cadr leaves)) (cddr leaves))))) ``` How can I make this code better and faster? And are there better ways of doing this?

I would like to reverse a list using cdr, car and cons. Since lists in lisp are asymmetrical (can only insert at the beginning), I am interested on how one would write a procedure to do that without using (append). Please review my code. ``` (define (reverse l) (define (aux orig result) (if (null? orig) result (aux (cdr orig) (cons (car orig) result)))) (aux l '())) ``` Is this good enough? Are there better or more efficient ways to do this?

A “perfect number” is defined as a number equal to the sum of all its factors less than itself. For example, the first perfect number is 6, because its factors are 1, 2, 3, and 6, and 1+2+3=6. The second perfect number is 28, because 1+2+4+7+14=28. What is the third perfect number? Write a procedure (next-perf n) that tests numbers starting with n and continuing with n+1, n+2, etc. until a perfect number is found. Then you can evaluate (next-perf 29) to solve the problem. Hint: you’ll need a sum-of-factors subprocedure. [Note: If you run this program when the system is heavily loaded, it may take half an hour to compute the answer! Try tracing helper procedures to make sure your program is on track, or start by computing (next-perf 1) and see if you get 6.] Source I am aware of Euclid's algorithm for solving this problem, but with the "n+1,n+2" part of the problem statement I think I shouldn't do that. So I did it in a brute force way. ``` (define (nextPerf n) (define (sumOfFactors a) (cond ((= n a) 0) ((= (remainder n a) 0) (+ a (sumOfFactors (+ a 1)))) (else (sumOfFactors (+ a 1))))) (if (= (sumOfFactors 1) n) n (nextPerf (+ n 1)))) ``` Is this good code? How can I make it better?

I am working on Problem 2.30 from Structure and Interpretation of Computer Programs. I book is in scheme, but I am doing the exercises in Clojure. The problem is to write code that takes a tree of numbers and return a new tree with the numbers squared. I have done it in two ways: - Without higher-order functions: ``` (defn square-tree1 [tree] (lazy-seq (when-let [s (seq tree)] (if (coll? (first s)) (cons (square-tree1 (first s)) (square-tree1 (rest s))) (cons (square (first s)) (square-tree1 (rest s))))))) ``` - Using map ``` (defn square-tree2 [tree] (if (coll? tree) (map square-tree2 tree) (square tree))) ``` Where: ``` (defn square [x] (* x x)) ``` My tests for this are: ``` (deftest e2.30a (testing "Ex 2.30a: square-tree" (is (= (square-tree1 (list 1 (list 2 (list 3 4) 5) (list 6 7))) '(1 (4 (9 16) 25) (36 49)))) (is (= (square-tree1 '()) '())) (is (= (square-tree1 [1 2 3 4 5]) [1 4 9 16 25])) (is (= (square-tree1 [1 [2 [3]]]) [1 [4 [9]]])))) ``` - I want the functions to work with lists and vector inputs. - I am unsure if 1 is the proper usage of lazy-seq and whether there is a neater way to express this. - Is `(col? (first s))` the correct predicate here? I find it tricky in Clojure to test if the node in the tree is another sub-tree or if it is number. In Scheme it is easier because you have the `pair?` predicate. I would like to see if there is a better way. Edit -- After a useful discussion with Timothy Pratley about clojure.walk After looking at the source code of clojure.walk I have come up with a third square-tree function that extends the square-tree2, but now preserves the input collection types of the input tree like clojure.walk does: ``` (defn square-tree3 [tree] (cond (list? tree) (apply list (map square-tree3 tree)) (seq? tree) (doall (map square-tree3 tree)

I am extremely new at scheme and I am doing this problem from here: Write a procedure switch that takes a sentence as its argument and returns a sentence in which every instance of the words I or me is replaced by you, while every instance of you is replaced by me except at the beginning of the sentence, where it’s replaced by I. (Don’t worry about capitalization of letters.) Example: (switch ’(You told me that I should wake you up)) (i told you that you should wake me up) I used additional functions from here. ``` (define (switchnext n) (cond ((empty? n) '()) ((or (equal? (first n) 'you) (equal? (first n) 'You)) (se 'me (switchnext (bf n)))) ((or (equal? (first n) 'i) (equal? (first n) 'I) (equal? (first n) 'me)) (se 'you (switchnext (bf n)))) (else (se (first n) (switchnext (bf n)))))) (define (switch n) (cond ((empty? n) '()) ((or (equal? (first n) 'you) (equal? (first n) 'You)) (se 'i (switchnext (bf n)))) (else (se (first n) (switchnext (bf n)))))) ``` I absolutely hate this code; I feel it is too repetitive. I think part of it is because I probably have no way of knowing when is beginning of a sentence. How can I improve this code?

Problem: Question 8: * Mergesort is a type of sorting algorithm. It follows a naturally recursive procedure: Break the input list into equally-sized halves Recursively sort both halves Merge the sorted halves. Using your merge function from the previous question, implement mergesort. Challenge: Implement mergesort itself iteratively, without using recursion. ``` def mergesort(seq): """Mergesort algorithm. >>> mergesort([4, 2, 5, 2, 1]) [1, 2, 2, 4, 5] >>> mergesort([]) # sorting an empty list [] >>> mergesort([1]) # sorting a one-element list [1] """ "*** YOUR CODE HERE ***" ``` Solution: ``` def merge_iter(lst1, lst2): """Merges two sorted lists recursively. >>> merge_iter([1, 3, 5], [2, 4, 6]) [1, 2, 3, 4, 5, 6] >>> merge_iter([], [2, 4, 6]) [2, 4, 6] >>> merge_iter([1, 2, 3], []) [1, 2, 3] >>> merge_iter([5, 7], [2, 4, 6]) [2, 4, 5, 6, 7] """ new = [] while lst1 and lst2: if lst1[0] >> merge_recur([1, 3, 5], [2, 4, 6]) [1, 2, 3, 4, 5, 6] >>> merge_recur([], [2, 4, 6]) [2, 4, 6] >>> merge_recur([1, 2, 3], []) [1, 2, 3] >>> merge_recur([5, 7], [2, 4, 6]) [2, 4, 5, 6, 7] """ if not lst1: return lst2 if not lst2: return lst1 if lst1[0] > lst2[0]: return [lst2[0]] + merge_recur(lst1, lst2[1:]) else: return [lst1[0]] + merge_recur(lst1[1:], lst2) def mergesort_recur(seq): """Mergesort algorithm. >>> mergesort_recur([4, 2, 5, 2, 1]) [1, 2, 2, 4, 5] >>> mergesort_recur([]) # sorting an empty list [] >>> mergesort_recur([1]) # sorting a one-element list [1] """ if not seq: return [] if(len(seq) == 1): return [seq[0]] middle = len(seq) // 2 left = mergesort_recur(seq[0:middle]) right = mergesort_recur(seq[middle:len(seq)]) return merge_recur(left, right) def middle(seq): r