;; Ques: Sorting an integer
;; Let’s say we wanted to sort an integer that is passed into an iterative function. This function
;; would make use of an auxiliary function, say — sorted-insert — which inserts a digit into an
;; already sorted integer.
;; Design idea
;; Let’s start with the sorted-insert function first for a bottom-up approach to this problem.
;; spec for sorted-insert
;; pre: n is a natural number which is already in <=-sorted order, d is a digit in the range [1,9]
;; post: returns the integer n with d inserted into it while maintaining <=-sorted order
;; Design variables for an iterative function:
;; We can consider a result-so-far value, say rsf, which stores the numbers already read
;; We'd also need a copy of this n value so we can iterate over it
;; Suggestion: We want to iterate over this copy of n, and when d is greater than the current digit
;; (namely n%10), we'll add d to the rsf and add the rest of unprocessed-n to rsf
;; If we want to do this, we'd also seem to need some sort of variable, say k, which keeps track of
;; the number of digits we already processed in n.
;; Given this new variable, we'd want to add d*10^k to rsf and n*____
;; To figure out this blank, let's work out an example:
;; (iter n k rsf) where d = 4
;; (iter 1234 0 0)
;; (iter 123 1 4)
;; 4 + 4*10^1 = 44 + 123*10^2 = 44 + 12300 = 12344
;; So this tells us we also want to add n*10^(k+1) when our function sees that the current digit
;; (n%10) is greater than d. And this gives us the result we want.
;; But what about our iterative calls?
;; Per the divide and conquer strategy of traversing a number, we take (quotient n 10), add
;; (n%10)*10^k to rsf, and k+1:
;; (iter (quotient n 10) (+ k 1) (+ rsf (* (modulo n 10) (expt 10 k))))
;; Code:
;; pre: n is a natural number which is already in <=-sorted order, d is a digit in the range [1,9]
;; post: returns the integer n with d inserted into it while maintaining <=-sorted order
(define (sorted-insert d n)
(define (iter n k rsf)
(cond ((> d (modulo n 10)) (+ rsf
(* d (expt 10 k))
(* n (expt 10 (+ k 1)))))
(else (iter (quotient n 10) (+ k 1) (+ (* (modulo n 10) (expt 10 k))
rsf)))))
(cond ((zero? d) n)
(else (iter n 0 0))))
;; How can we use this function to develop a sort function which sorts an integer n?
;; Assuming sorted-insert works properly, we can use an iterative function which uses a copy of n
;; and an rsf:
;; n – contains the unprocessed digits of N (N is the initial value passed into the wrapper)
;; rsf – contains the processed digits of N in sorted order
;; This iterative function can traverse the digits of n one at a time and add to rsf the current digit
;; while maintaining sorted order.
;; This tells us we’d have something like:
;; (iter n rsf)
;; We want to divide n by taking (modulo n 10) and using sorted-insert to insert this current digit
;; into rsf. In order to traverse n, we’d then take (quotient n 10) on subsequent calls. The function
;; would be done when n is 0, we can return rsf.
;; Code
;; pre: n is a natural number
;; post: returns the same n but in sorted order
(define (sort n)
(define (iter n rsf)
(cond ((zero? n) rsf)
(else (iter (quotient n 10) (sorted-insert (modulo n 10) rsf)))))
(iter n 0))
;; Testing
(display “Testing sort:\n”)
(sort 432198765)
;; Proof(s):
;; Proofs would need to be given for both sorted-insert and sort. Keep in mind that both require
;; guess invariants to be proven. And as usual, with any guess invariants, we prove that they are
;; actually invariant by using the test suite provided in class.
;; GI (sorted-insert):
;; GI (sort):
;; Given that we only have an hour left, I’ll leave this for you guys to solve for now. If we have
;; time at the end, we can go back to this part of the solution.
;; Since we did not get to this proof during the session, I’d highly recommend working on developing
;; GIs for both functions and testing them. It might be easier to start these functions from the
;; ground up so that you can come up with a GI. Feel free to send me an email or message if you want
;; me to take a look at your GI. I will try my best to get to it before Monday night.
;;; Ques: Topics for Level 1
;; Lectures
; Lectures 1-6 from the lecture outlines
;; Homework
; Homework 1-3
; Homework 1 – functional decomposition and basic recursion vs. iteration
; Homework 2 – more recursion and iteration with integer decompositions (plus tree recursions)
; Homework 3 – higher order functions (I recommend problems 1.41-1.43 and drawing out the trace of
; the lambda substitutions for your higher order functions in these problems)
;; Practice Problems
; Practice problems 1 & 2
; Practice problem 1 – functional decomposition without recursion
; Practice problem 2 – reverse-digits which requires decomposition of integers and recursion
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(sort 123400059)