From bfdca48dadb73362e2ce28314c7138986110e236 Mon Sep 17 00:00:00 2001 From: Ramakrishnan Muthukrishnan <vu3rdd@gmail.com> Date: Sun, 12 Sep 2010 23:41:46 +0530 Subject: [PATCH] solutions to 2.{64,65,66} --- src/sicp/ex2_64.clj | 38 ++++++++++++++++++++++++++++++++++++++ src/sicp/ex2_65.clj | 16 ++++++++++++++++ src/sicp/ex2_66.clj | 9 +++++++++ 3 files changed, 63 insertions(+) create mode 100644 src/sicp/ex2_64.clj create mode 100644 src/sicp/ex2_65.clj create mode 100644 src/sicp/ex2_66.clj diff --git a/src/sicp/ex2_64.clj b/src/sicp/ex2_64.clj new file mode 100644 index 0000000..ad581f8 --- /dev/null +++ b/src/sicp/ex2_64.clj @@ -0,0 +1,38 @@ +(ns sicp.ex2_64 + (:use [sicp.ch2_3 :only (make-tree)])) + +(declare partial-tree) + +(defn list->tree [elements] + (first (partial-tree elements (count elements)))) + +(defn partial-tree [elts n] + (if (= n 0) + (cons '() elts) + (let [left-size (quot (- n 1) 2) + left-result (partial-tree elts left-size) + left-tree (first left-result) + non-left-elts (rest left-result) + right-size (- n (+ left-size 1)) + this-entry (first non-left-elts) + right-result (partial-tree (rest non-left-elts) right-size) + right-tree (first right-result) + remaining-elts (rest right-result)] + (cons (make-tree this-entry + left-tree + right-tree) + remaining-elts)))) + +(comment + "partial-tree divides the input sequence roughly into 2 halfs and creates a tree of + partial-trees on each of the branches." + "The tree for the input '(1 3 5 7 9 11) looks like this:" + " + 5 + / \ + 1 9 + \ / \ + 3 7 11 + " + "partial-tree does a cons for every element of the list. So, order of growth is O(n)." +) \ No newline at end of file diff --git a/src/sicp/ex2_65.clj b/src/sicp/ex2_65.clj new file mode 100644 index 0000000..918f958 --- /dev/null +++ b/src/sicp/ex2_65.clj @@ -0,0 +1,16 @@ +(ns sicp.ex2_65 + (:use [sicp.ex2_63] + [sicp.ex2_64] + [sicp.ex2_62 :only (union-set)] + [sicp.ch2_3 :only (intersection-set)])) + +(defn union-set-tree [set1 set2] + (let [ls1 (tree->list-1 set1) + ls2 (tree->list-1 set2)] + (list->tree (union-set ls1 ls2)))) + + +(defn intersection-set-tree [set1 set2] + (let [ls1 (tree->list-1 set1) + ls2 (tree->list-1 set2)] + (list->tree (intersection-set ls1 ls2)))) \ No newline at end of file diff --git a/src/sicp/ex2_66.clj b/src/sicp/ex2_66.clj new file mode 100644 index 0000000..9185621 --- /dev/null +++ b/src/sicp/ex2_66.clj @@ -0,0 +1,9 @@ +(ns sicp.ex2_66) + +(defn lookup [given-key set-of-records] + (if (empty? set-of-records) + false + (let [record (entry set-of-records)] + (cond (= given-key (get-key record)) record + (< given-key (get-key record)) (lookup given-key (left-branch set-of-records)) + (> given-key (get-key record)) (lookup given-key (right-branch set-of-records)))))) \ No newline at end of file -- 2.45.2