<esc> p | prev expr in interactions window. Note <esc> then p |
<esc> n | next expr |
Fn-F5 | run |
^p | prev |
^n | next |
^a | start of line |
^e | end of line |
#lang racket
(define (f x y) (+ x y))
; This is a box comment, which creates
; an unreadable .rkt file
when the last two lines are made into a box comment creates a 263 line file of 8770 characters! Here is some of it. It makes you yearn for the simple concise expressivity of XML. code/Week01/badbox.rkt |# |
30 7 #"wxtext\0" |
3 1 6 #"wxtab\0" |
1 1 8 #"wximage\0" |
2 0 8 #"wxmedia\0" |
4 1 34 #"(lib \"syntax-browser.ss\" \"mrlib\")\0" |
1 0 16 #"drscheme:number\0" |
3 0 44 #"(lib \"number-snip.ss\" \"drscheme\" \"private\")\0" |
1 0 36 #"(lib \"comment-snip.ss\" \"framework\")\0" |
1 0 93 |
( |
#"((lib \"collapsed-snipclass.ss\" \"framework\") (lib \"collapsed-sni" |
#"pclass-wxme.ss\" \"framework\"))\0" |
) 0 0 43 #"(lib \"collapsed-snipclass.ss\" \"framework\")\0" |
0 0 19 #"drscheme:sexp-snip\0" |
0 0 36 #"(lib \"cache-image-snip.ss\" \"mrlib\")\0" |
1 0 68 |
( |
list2
and list3
that construct lists of 2 and 3 elements respectively. For example (list2 2 3)
is the list (2 3)
(list3 1 5 7)
is the list (1 5 7)
fmap
and freduce
functions. fmap
operator takes a unary function fn
and a list L
, and (fmap fn L)
returns the list resulting from applying fn
to each element of L
. For example, (fmap (lambda (x) (< x 5)) '(1 7 3 5 7 9))
(#t #f #t #f #f #f)
freduce
operator takes an associative binary function op
, an identity element e
for op, and a list L
. Then (freduce op e L)
computes the result of inserting op between each element of the list. The identity element is the result of reducing an empty or one element list. (freduce + 0 '(4 5 6))
lequal
that tests if two lists are equal. This means that they have the same structure and their atoms (leaves) match. For example: (lequal 1 1)
(lequal '() '())
(lequal '(1) '(1))
(lequal '(1 (2) (3 4)) '(1 (2) (3 4)))
and these all return false (lequal 1 '())
(lequal '() 1)
(lequal '() '(1))
(lequal '(1) '())
(lequal '(1) '(2))
NOTE: You can assume that only integers appear as atoms in the lists. (genindex n)
that generates a list consisting of the indexes (0 1 2 ... n-1)
. That is, the indexes that you would use to index into an n element array. Implement the function(genindex 0)
is()
(genindex 1)
is(0)
(genindex 4)
is(0 1 2 3)
(genseq low high inc)
that generates a list consisting of the integers (low low+inc low+inc+inc ... high)
For example NOTE: think about how(genseq 2 5 1)
is(2 3 4 5)
(genseq 10 20 7)
is(10 17)
(genseq 8 7)
is( )
fmap
relates genindex
and genseq
. You can use fcompose
also if you want. ( (1 2) (1 2) )
simplifies to (1 2)
, while this (1 (2 2))
simplifies to (1 2)
( (1 (2 2)) (1 (2) ) )
simplifies to ( (1 2) (1 (2) ) )
which then further simplifies to ( (1 2) (1 2) )
which then simplifies to (1 2)
(simplify T)
which does this. #lang scheme |
|
; part 1 |
|
(define list2 (lambda (e1 e2) (cons e1 (cons e2 '())))) |
(define list3 (lambda (e1 e2 e3) (cons e1 (cons e2 (cons e3 '() ))))) |
|
; part 2 - map and reduce |
|
(define fmap (lambda (fn L) |
(if (null? L) |
'() |
(cons (fn (first L)) (fmap fn (rest L))) |
)) |
) |
|
; compare the run-time stacks of these two solutions |
|
; non-tail recursive - there is still work to do after the recursive call |
(define freduce-non-tail (lambda (identity fn L) |
(if (null? L) |
identity |
(fn (first L) (freduce identity fn (rest L))) |
))) |
|
; tail recursive solution |
(define freduce (lambda (left-accumulate fn L) |
(if (null? L) |
identity |
(freduce (fn left-accumulate (first L)) fn (rest L)) |
))) |
|
|
; part 3 - deep list equality |
|
(define both-are-lists? (lambda (x y) |
(and (list? x) (list? y)) |
)) |
|
(define both-are-null? (lambda (x y) |
(and (null? x) (null? y)) |
)) |
|
(define both-are-not-null? (lambda (x y) |
(and (not (null? x)) (not (null? y)) ) |
)) |
|
(define both-are-numbers? (lambda (x y) |
(and (number? x) (number? y)) |
)) |
|
(define lequal? (lambda (x y) |
(if (both-are-lists? x y) |
(if (both-are-not-null? x y) |
(and |
(lequal? (first x) (first y)) |
(lequal? (rest x) (rest y)) |
) |
(both-are-null? x y) |
) |
(if (both-are-numbers? x y) |
(= x y) |
#f |
) |
) |
)) |
|
|
; part 4 - list construction |
|
(define genindex (lambda (n) (genindex_r 0 n))) |
(define genindex_r (lambda (i n) |
(if (>= i n) |
'() |
(cons i (genindex_r (+ 1 i) n)) |
))) |
|
|
(define genseq (lambda (low high inc) |
(fmap (lambda (i) (+ low (* i inc))) |
(genindex (+ 1 (quotient (- high low) inc) ) ) |
) |
)) |
|
|
; part 5 binary tree simplification |
|
; if L and R are different return (L R) else return L |
(define simplify_pair (lambda (L R) |
(if (lequal? L R) |
L |
(list2 L R) |
) |
)) |
|
|
(define simplify |
(lambda (L) |
(if (not (list? L)) |
; non-lists are already simple |
L |
(if (null? L) |
; empty lists are simple |
L |
(if (null? (rest L)) |
; 1 element lists are replaced by simplified first element |
(simplify (first L)) |
(if (null? (rest (rest L))) |
; 2 element lists need the pair simplified |
(simplify_pair (simplify (first L)) |
(simplify (second L))) |
; > 2 element lists have their terms simplified, but |
; can't be simplified at the node since they are not |
; binary trees |
(fmap simplify L) |
) |
) |
) |
))) |
|
(simplify '((1 1) (1 (1 1)))) |
(fmap2 fn X Y)
that takes a 2-argument function fn
, and two lists X
and Y
, and produces a new list that results from applying fn
to corrsponding elements of X
and Y
. (fmap fn X Y)
is the list ( (fn x_0 y_0) (fn x_1 y_1) ... (fn x_n y_n) )
(fmap2 min '(1 2 3 4 5) '(0 3 2 4 6))
is(0 2 2 4 5)
(fmap2 min '(1 2 3) '(0 3 2 4 6))
is(0 2 2)
fmapc
which does the same as fmap
, but if the lists are different lengths, then when the shorter one runs out, additional elements are taken from the beginning of the shorter list, cycling until the longer list is complete. (fmap2c + '(1 2 3 4 5) '(0 1))
is(1 3 3 5 5)
(fmap2c + '(1 2 3 4 5 6 7) '())
is'()
(fmap2c + '(1 2 3 4 5 6 7) '(1))
is'(2 3 4 5 6 7 8)
(fmap2c + '(1 2 3 4 5 6 7) '(1 2 3 4 5 6))
is'(2 4 6 8 10 12 8)
3. Week 1 - Jan 6 CMPUT 325 Schedule / Version 2.31 2014-04-04 |