Navigation
index
next |
previous |
383summer2019 documentation
Assignment 1: Learning Scheme
In this assignment, your task is to learn basic Scheme programming. Well do this by implementing a number of basic Scheme functions.
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, equal?
basic arithmetic operators like +, /, mod, <, >=,
data types: numbers, strings, symbols, 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.
Functions that start with my- are versions of existing Scheme functions. Of course, dont use the existing Scheme function in your code!
1.Implement a function called (singleton? x) that returns #t if x is a list with exactly 1 element, and #f otherwise. For example:> (singleton? (4 mouse ()))
2.#f
3.
4.> (singleton? (xy))
5.#t
6.
7.> (singleton? 4)
8.#f
9.
10.Implement a function called (my-make-list n x) that returns a list containing n copies of x. For example:> (my-make-list 3 a)
11.(a a a)
12.
13.> (my-make-list 2 (1 2 3))
14.((1 2 3) (1 2 3))
15.
16.> (my-make-list 2 (my-make-list 3 (a b)))
17.(((a b) (a b) (a b)) ((a b) (a b) (a b)))
18.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.
19.Implement a function called (all-same? lst) that returns #t if lst is empty, or if all the elements in it are equal to each other (using equal?). For example:> (all-same? ())
20.#t
21.
22.> (all-same? (cat))
23.#t
24.
25.> (all-same? (cat cat cat))
26.#t
27.
28.> (all-same? (cat cat dog cat))
29.#f
30.You can assume lst is a valid list. If its not, its fine if your function crashes.
31.Implement a function called (my-iota n) that returns a list containing the numbers from 0 to n-1. For example:> (my-iota 0)
32.()
33.
34.> (my-iota 1)
35.(0)
36.
37.> (my-iota 2)
38.(0 1)
39.
40.> (my-iota 5)
41.(0 1 2 3 4)
42.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.
43.Implement a function called (my-length lst) that returns that returns the number of items in lst. For example:> (my-length ())
44.0
45.
46.> (my-length (a))
47.1
48.
49.> (my-length (a (b c)))
50.2
51.
52.> (my-length (a (b c) d))
53.3
54.You can assume lst is a valid list. If its not, its fine if your function crashes.
55.Implement a function called (nth lst i) that returns that returns the item at index location i in lst. 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)
56.a
57.
58.> (nth (a b c) 1)
59.b
60.
61.> (nth (a b c) 2)
62.c
63.
64.> (nth (a b c) 3)
65.;bad index
66.You can assume lst is a valid list and i is a valid integer. If not, its fine if your function crashes.If i is less than 0, or if its greater than or equal to the length of lst, call the error function.
67.Implement a function called (my-last lst) that returns the last element of lst. For example:> (my-last (cat))
68.cat
69.
70.> (my-last (cat dog))
71.dog
72.
73.> (my-last (cat dog (1 2 3)))
74.(1 2 3)
75.
76.> (my-last ())
77.my-last: empty list
78.Notice that calling my-last on the empty list prints the error message my-last: empty list. Use the error 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.
79.Implement a function called (middle lst) that returns a list that is the same as lst, but the first element and the last element have been removed. For example:> (middle (a b c d e))
80.(b c d)
81.
82.> (middle (6 4 cat m egg))
83.(4 cat m)
84.If lst has 2, or fewer, elements, then return the empty list.You can assume lst is a valid list. If its not, its fine if your function crashes.
85.Implement a function called (my-filter pred lst) that returns a list containing just the elements of lst that satisfied the predicate function pred. For example:> (my-filter odd? (5 7 0 -6 4))
86.(5 7)
87.
88.> (my-filter odd? (10 5 7 0 11 4))
89.(5 7 11)
90.
91.> (my-filter list? (hat (left right) 4 ()))
92.((left right) ())
93.
94.> (my-filter (lambda (x) (or (= x 5) (< x 0))) ‘(5 6 9 -6 2 5 0 5))95.(5 -6 5 5)96.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.97.Implement a function called (my-append A B) that returns a list that has all the elements of A followed by all the elements of B. For example:> (my-append (1 2 3) (4 5 6 7))
98.(1 2 3 4 5 6 7)
99.
100.> (my-append (1 2 3) (4))
101.(1 2 3 4)
102.
103.> (my-append () (4))
104.(4)
105.You can assume A and B are valid lists. If theyre not, its fine if your function crashes.
106.Implement a function called (append-all lol) that returns a list that has all the lists of lol appended into one list. For example:> (append-all ())
107.()
108.
109.> (append-all ((a)))
110.(a)
111.
112.> (append-all ((a) (b c)))
113.(a b c)
114.
115.> (append-all ((a) (b c) (d)))
116.(a b c d)
117.
118.> (append-all ((a) (b c) (d) (e f)))
119.(a b c d e f)
120.You can assume lol a valid list of lists, i.e. lol is a list whose elements are all lists. If lol is not a list of lists, its fine if your function crashes.
121.Implement a function called (my-sort lst) that returns the numbers on lst in sorted order. For example:> (my-sort ())
122.()
123.
124.> (my-sort (3))
125.(3)
126.
127.> (my-sort (4 1 3 7 5 5 1))
128.(1 1 3 4 5 5 7)
129.You can assume lst a valid list of numbers. If 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
130.Implement a function called (all-bits n) that returns a list of 2n2nsub-lists, where each sub-list is a different pattern of n 0s and 1s. For example:> (all-bits 0)
131.()
132.
133.> (all-bits 1)
134.((0) (1))
135.
136.> (all-bits 2)
137.((0 0) (0 1) (1 0) (1 1))
138.The order of the sub-lists doesnt matter, as long the returned list contains exactly all 2n2npossible 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 of n.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.
What to Submit
Put all your code into a single Scheme source file called a1.scm, and this submit this online in Canvas.
Please make sure to use exactly the function names and inputs as described above, otherwise your functions will get marked as incorrect.
Table Of Contents
Assignment 1: Learning Scheme
What to Submit
Previous topic
Welcome to CMPT 383, Summer 2019!
Next topic
Assignment 2
Quick search
Navigation
index
next |
previous |
383summer2019 documentation
Copyright 2019, Toby Donaldson. Created using Sphinx 1.7.9.
Reviews
There are no reviews yet.