COSC 3410 Programming Languages

Fall 2011

Homework Assignment #3

Revenge of the Scheme

Due: Wednesday, Sept 21, 11:00am CDT
Submit: Turn in a single Scheme source file called "hw3.scm" using the turnin command on the Systems Lab machines. Include the names of all authors at the top of the file in a comment block. Work is to be completed individually. This assignment makes use of the Binary Tree Demo from class. To use these definitions for your assignment, download the Tree.scm source file into the same directory as your hw3.scm file. Include at the top of your hw3.scm file:

(require "Tree.scm")

Do not turnin Tree.scm with your assignment; I will provide my own copy when grading.

Q1 - swap*

swap* : Atom x Atom x S-List → S-List
Usage: (swap* a b slst) = slst with all occurrences of atom "a" replaced with "b", and all occurrences of atom "b" replaced with "a".

Examples:
> (swap* 'foo 'bar '())
()
> (swap* 'foo 'bar '(foo bar baz bar foo))
(bar foo baz foo bar)
> (swap* 'a 'b '(foo b (bar a (c d (b)) a) e))
(foo a (bar b (c d (a)) b) e)

Q2 - filter-in

filter-in : Predicate x List → List
Usage: (filter-in pred lst) = lst with each atom that returns true when the "pred" is applied filtered out.
Examples:
> (filter-in zero? '(1 2 ((0)) ((3) 0 4) 5 (0 (6)) 0))
(1 2 (()) ((3) 4) 5 ((6)))
> (filter-in (lambda (x) (eq? 'a x)) '(a b c a d e))
(b c d e)
> (filter-in null? '(a (b (c ()))))
(a (b (c)))

Q3 - sort

sort : ListOf(Int) → ListOf(Int)
Usage: (sort loi) = loi with the integers sorted into ascending order.
Examples:
> (sort '(1))
(1)
> (sort '(1 2 3))
(1 2 3)
> (sort '(3 2 1 2 3 2 1))
(1 1 2 2 2 3 3)

Q4 - double-tree

double-tree : BinaryTree(Int) → BinaryTree(Int)
Usage: (double-tree t) = new binary tree with same structure as t, but with each integer contained within the tree doubled.
This problem relies upon the binary tree demonstration from lecture. See above.

Examples:
> (double-tree (tree-make-null))
(tree)
> (double-tree (tree-add 3 (tree-add 5 (tree-add 7 (tree-make-null)))))
(tree 14 (tree 10 (tree 6 (tree) (tree)) (tree)) (tree))

Q5 - path

path : Int x BinaryTree(Int) → S-List
Usage: (path n t) = lst, a list of lefts and rights showing how to reach the node in t that contains n.
This problem relies upon the binary tree demonstration from lecture. See above.

Examples:
> (path 3 (tree-add 5 (tree-add 3 (tree-add 7 (tree-make-null)))))
(left)
> (path 5 (tree-add 5 (tree-add 3 (tree-add 7 (tree-make-null)))))
(left right)
> (path 7 (tree-add 5 (tree-add 3 (tree-add 7 (tree-make-null)))))
()
> (path 2 (tree-add 5 (tree-add 3 (tree-add 7 (tree-make-null)))))
#f