;; An Los (list of string) is one of
;; -- '()
;; -- (cons String Los)
| Los | ::= |
'()
|
| ::= |
(cons String Los)
|
|
|
car and cdr
define-datatype and cases
disk-usage that takes as
input a Filesystem and produces the total size occupied by all its
files.
Before you start thinking of a solution, read and understand the
specification. A good way to go about this is to make examples of
valid Filesystems following the specification.
;; A Filesystem is one of
;; - EmptyFS
;; - (nonemptyfs FSElement Filesystem)
;; EmptyFS is (emptyfs)
;; An FSElement is one of
;; - File
;; - Directory
;; - SymbolicLink
;; A File is (file String Number)
;; (file s n) creates a file with name s and size n
;; A Directory is (dir String String Number Filesystem)
;; (dir s1 s2 n fs) creates the directory s1 owned by user s2
;; with size n and contents fs.
;; Invariant: n = (size fs)
;; A SymbolicLink is (slink String String)
;; (slink s1 s2) creates a link with name s1 pointing to s2
The implementation of the filesystem datatype was given using
define-datatype. Any code that expects a filesystem should
deal with all of its variants. In fact, the function's body is patterned after the
datatype's definition, follow the grammar!
|
(define-datatype filesystem filesystem?
(define-datatype fselement fselement? |
|
;; disk-usage: Filesystem -> Number ;; usage : (disk-usage fs) ;; produces : sum of size field for all files in fs (define disk-usage (lambda (fs) (cases filesystem fs [emptyfs () 0] [nonemptyfs (e f) (+ (fselement-du e) (disk-usage f))]))) ;; fselement-du : FSElement -> Number ;; usage : (fselement-du e) ;; produces : size occupied by e, for file return size field, ;; for dir the sum of size fields for all files in ;; contents field (define fselement-du (lambda (e) (cases fselement e [file (n s) s] [dir (n w s fs) (disk-usage fs)] [slink (s t) 0]))) |
;; WordTree ::= EmtpyTree
;; ::= (word-node String WordTree WordTree)
;; invariant: for any given (word-node w l r), words in l are
;; lexicographically less than w.
;; AND for any given (word-node w l r), words in r are
;; lexicographically greater than w.
;; Note: w > EmptyTree => #t
;; w < EmptyTree => #t
;; EmptyTree is special!
(define-datatype wordtree wordtree?
[emptytree]
[word-node (w string?)
(l wordtree?)
(r wordtree?)])
An invariant is a property that we expect to be true of any instance of our
datatype throughout our program. Each operation on this datatype has to thus ensure
that this property is not violated.
w and returns
#t if w is already in wordtree and #f otherwise.
[You can use string=?
string>? and string<? ]
w and produces
a new wordtree with w included in it.
Make sure your resulting wordtree does not violate the invariant.
w
and produces a new wordtree with w removed from the wordtree.
Make sure your resulting wordtree does not violate the invariant.
average that takes as
input a list of Numbers and produces their average. [We
will reuse this function later on in this lab]
map function
is a really useful one to know. Here is a way to specify what map does.
map f '(x1 x2 ... xn)) =
'(f(x1) f(x2) ... f(xn))
map
(map lst-length '((1 2) ("a" "b" "c") ('d 'f 'g 'h 'k)))
> '(2 3 5)
(map (lambda (x) (+ x 1)) '(1 2 3 4 5))
> '(2 3 4 5 6)
Homework from the previous lab (link).
Design a function that takes in a list of Homeworks and produces the average
grade of all homeworks. Your function should use map and average from
question 6 above.
Assignment from the previous lab (link). Design a
function that takes in a list of Assignments and produces the average grade of all
assignments. Your function should use map and average from question 6 above.
students-average that takes as input a list of lists
of Homework and the name of a student and calculates
the student's average grade. [Hint: First
design a function that picks the student's homework given a name out of a list of
Homeworks, the you can use your average function and
map.]
i) and
returns the element of the list at position i. Assume that the integer given is always
greater than 0 and less than or equal to the list's size.
Los design a function called
lst-length that consumes an Los and produces
its length.
;; An Los is one of ;; --'() ;; -- (cons String Los)Look at your contract for
lst-length. Even though you designed
lst-length to deal only with Los your function can
also produce the length of any list of scheme values! So what is the
contract for los-length?
What other kinds of lists can we give to lst-length
|
;; An Loi is one of ;; -- '() ;; -- (cons Integer Loi) |
;; An Loc is one of ;; -- '() ;; -- (cons Char Loc) |
;; An Losym is one of ;; -- '() ;; -- (cons Symbol Losym) |
;; An Loh is one of ;; -- '() ;; -- (cons Homework Loh) |
;; A [Listof X] is one of
;; -- '()
;; -- (cons X [Listof X])
[Listof X] is called
a polymorphic datatype.
So the contract for lst-length can now be written as
;; lst-length : [Listof X] -> Number ;; usage : (lst-length lst) ;; produces : number of elements in lst
[Listof X] is said to be
polymorphic in α.
car
and cdr.
cons.
map or every? from this weeks machine
problem.
Let's try and design the function twice which takes in
a function of one argument X -> X, an argument and applies
the function to the argument twice, e.g.
;; add1 : Number -> Number
;; usage : (add1 x)
;; purpose : increment x by 1
(define add1
(lambda (x)
(+ x 1)))
> (twice add1 3)
> 5
How should we write the contract for twice?
;; twice : ...
;; usage : (twice f a)
;; purpose : f(f(a))
(define twice
(lambda (f a)
...))
We could also write combine that takes in 2 functions
f1 and f2, both one argument
functions, and an argument a and produces the
result obtained by applying f1 to the result of
f2(a).
;; combine : ...
;; usage : (combine f1 f2 a)
;; purpose : f1(f2(a))
(define combine
(lambda (f1 f2 a)
...))
map.
ormap that consumes
a one argument function f that produces a Boolean
and a list. Your ormap has to produce a
Boolean by logically or-ing the results obtained by
applying f to each element of the list, e.g.,
(ormap even? '(2 5 6))
>#t
(ormap even? '(1 3 7))
> #f