In this assignment, your task is to learn basic Schemeprogramming. Well do this by implementing a number of basic Schemefunctions.
Your solutions are restricted to use only the following:
-
define
,lambda
,let
,let*
,cond
/else
,if
-
null?
,car
,cdr
,cons
,list?
,list
-
not
,and
,or
,#t
,#f
- arithmetic operators like
+
,/
,mod
,<
,>=
, - data types: numbers, strings, lists
Any functions you define in this assignment must use only these elementary forms. You can (should!) create helper functions, and you may also use functions from previous questions in the answers to later questions.
Many of the functions you are asked to implement are versions of existing Schemefunctions. Those functions start with my-
.
-
Implement a function called
(singleton? x)
that returns#t
ifx
has exactly 1 element,#f
otherwise. For example:> (singleton? '(4 mouse ()))#f> (singleton? '(xy))#t> (singleton? 4)#f
-
Implement a function called
(my-make-list n x)
that returns that returns list of containingn
copies ofx
. For example:> (my-make-list 3 'a)(a a a)> (my-make-list 2 '(1 2 3))((1 2 3) (1 2 3))> (my-make-list 2 (my-make-list 3 '(a b)))(((a b) (a b) (a b)) ((a b) (a b) (a b)))
If
n
is 0 or less, then return the empty list.You can assume
n
is a valid integer. If its not, its fine if your function crashes. -
Implement a function called
(my-iota n)
that returns a list containing the numbers from 0 to n-1. For example:> (my-iota 0)()> (my-iota 1)(0)> (my-iota 2)(0 1)> (my-iota 5)(0 1 2 3 4)
If
n
is 0 or less, then return the empty list.You can assume
n
is a valid integer. If its not, its fine if your function crashes. -
Implement a function called
(my-len lst)
that returns that returns the number of items inlst
. For example:> (my-len '())0> (my-len '(a))1> (my-len '(a (b c)))2> (my-len '(a (b c) d))3
You can assume
lst
is a valid list. If its not, its fine if your function crashes. -
Implement a function called
(nth lst i)
that returns that returns the item at index locationi
inlst
. The indexing is 0-based, so, the first element is at index location 0, the second element is at index location 1, and so on. For example:> (nth '(a b c) 0)a> (nth '(a b c) 1)b> (nth '(a b c) 2)c> (nth '(a b c) 3);bad index
You can assume
lst
is a valid list. If its not, its fine if your function crashes.If
i
is less than 0, or if its greater than or equal to the length oflst
, call theerror
function.You can assume
i
is a valid integer. If its not, its fine if your function crashes. -
Implement a function called
(my-last lst)
that returns the lastelement oflst
. For example:> (my-last '(cat))cat> (my-last '(cat dog))dog> (my-last '(cat dog (1 2 3)))(1 2 3)> (my-last '())my-last: empty list
Notice that calling
my-last
on the empty list prints the error message my-last: empty list. Use theerror
function to do this, e.g.(error "my-last: empty list")
.You can assume
lst
is a valid list. If its not, its fine if your function crashes. -
Implement a function called
(my-filter pred lst)
that returns a list containing just the elements oflst
that satisfied the predicate functionpred
. For example:> (my-filter odd? '(5 7 0 -6 4))(5 7)> (my-filter odd? '(10 5 7 0 11 4))(5 7 11)> (my-filter list? '(hat (left right) 4 ()))((left right) ())> (my-filter (lambda (x) (or (= x 5) (< x 0))) '(5 6 9 -6 2 5 0 5))(5 -6 5 5)
You can assume
pred
is a predicate function that takes one input, and returns either#t
or#f
. If its not, its fine if your function crashes.You can assume
lst
is a valid list. If its not, its fine if your function crashes. -
Implement a function called
(my-append A B)
that returns a list that has all the elements ofA
followed by all the elements ofB
. For example:> (my-append '(1 2 3) '(4 5 6 7))(1 2 3 4 5 6 7)> (my-append '(1 2 3) '(4))(1 2 3 4)> (my-append '() '(4))(4)
You can assume
A
andB
are valid lists. If theyre not, its fine if your function crashes. -
Implement a function called
(append-all lol)
that returns a list that has all the lists oflol
appended into one list. For example:> (append-all '())()> (append-all '((a)))(a)> (append-all '((a) (b c)))(a b c)> (append-all '((a) (b c) (d)))(a b c d)> (append-all '((a) (b c) (d) (e f)))(a b c d e f)
You can assume
lol
a valid list of lists, i.e.lol
is a list whose elements are all lists. Iflol
is not a list of lists, its fine if your function crashes. -
Implement a function called
(my-sort lst)
that returns the numbers onlst
in sorted order. For example:> (my-sort '())()> (my-sort '(3))(3)> (my-sort '(4 1 3 7 5 5 1))(1 1 3 4 5 5 7)
You can assume
lst
a valid list of numbers. Iflol
its not, its fine if your function crashes.Its fine if your algorithm runs in quadratic time.
Hint: Recursive sorting algorithms, like quicksort or mergesort, are good choices for Scheme
-
Implement a function called
(all-bits n)
that returns a list of 2n sub-lists, where each sub-list is a different pattern ofn
0s and 1s. For example:> (all-bits 0)()> (all-bits 1)((0) (1))> (all-bits 2)((0 0) (0 1) (1 0) (1 1))
The order of the sub-lists doesnt matter, as long the returned list contains exactly all 2n possible bit lists.
Important: your function should, at least in theory, work for any
n
no matter how big. Do not use any tricks that assume a limit on the size ofn
.If
n
is less than or equal to 0, return the empty list.You can assume
n
is a valid integer. If its not, its fine if your function crashes.
Reviews
There are no reviews yet.