Mergesort in Racket #
Mergesort breaks the list in half and sorts each half recursively.
Some pseudo:
ms(list)
front = front half of list
back = back half of list
ms(front)
ms(back)
return merge(front, back)
In racket, there is a function called drop
that takes a list and a number. It drops the numbers off the list.
There is also take
, that takes the first number of elements of the list and returns them.
(define list '(1 2 3 4 5 6)) ; helper definition
(drop list 2) ; '(3 4 5 6)
(take list 2) ; '(1 2)
(drop list (quotient (length list) 2)) ; drops the first half of the list
So we can start our mergesort definition:
(define (ms xs)
(if (< (length xs) 2)
xs
(merge (ms (take xs (quotient (length xs) 2)))
(ms (drop xs (quotient (length xs) 2))))))
However, we haven’t defined merge
yet, so:
(define (merge xs ys)
(cond ((empty? xs) ys)
((empty? ys) xs)
((< (first xs) (first ys)) (cons (first xs) (merge (rest xs) ys)))
(else (cons (first ys) (merge (rest ys) xs)))))
So we can test this:
(ms '(5 3 6 2 7 1 4)) ; '(1 2 3 4 5 6)
Higher-order functions #
Treat functions as first class data. We’re going to allow functions to be passed as parameters. We’ll consider 3 functions that take functions as parameters.
(map f xs)
– appliesf
to each element ofxs
, and builds a list from the results(filter f xs)
–f
is a boolean, it appliesf
to each element ofxs
and filters out any element for whichf
is false(foldl f acc xs)
– abstracts the acumulator process we did earlier. It appliesf
to each value ofxs
and integrates that value into the accumulatoracc
. Thel
infoldl
means that it is going from left to right.foldl
is \( O(n) \) .
For example, to sum the elements of a list using foldl
:
(foldl + 0 xs) ; 10
Examples using map
:
(map add1 '(1 2 3 4)) ; '(2 3 4 5)
We can use our own functions in map
(define (double x)
(+ x x))
(map double '(1 2 3 4)) ; '(2 4 6 8)
Lets take a look at filter
:
(filter even? '(1 2 3 4 5)) ; '(2 4)
Designing filter
#
The base case is the empty list, which returns back the empty list.
When we are calling the function recursively, we will have to use rest
.
Heres a screenshot using even?
as f
:
; my-filter applies f to each element of xs
; and builds a list from those that make f true
; f: A --> boolean
; xs: list of A
(define (my-filter f xs)
(if (empty? xs)
empty
(if (f (first xs)) ; remember f is a function
(cons (first xs) (my-filter f (rest xs)))
(my-filter f (rest xs)))))
So:
(my-filter even? '(1 2 3 4 5)) ; '(2 4)
Designing foldl
#
Recall
(foldl + 0 '(1 2 3 4)) ; 10
; f: (A, B) --> A
; acc: A
; xs: list of B
(define (my-foldl f acc xs)
(if (empty? xs)
acc
(my-foldl f (f acc (first xs)) (rest xs))))
So lets test it:
(my-foldl + 0 '(1 2 3 4)) ; 10
Lambda functions #
Lambdas are nameless (anonymous) functions.
(lambda (x y)
(+ x y))
How can we call this function if it doesn’t have a name? There are many uses, we can define an operation without writing the full definition.
For example, to double all the numbers of a list:
(define (double-all xs)
(if (empty? xs)
empty
(cons (* 2 (first xs)) (double-all (rest xs)))))
(double-all '(1 2 3)) ; '(2 4 6)
But we can do this with higher order functions:
(define (double x)
(* 2 x))
(define (double-all2 xs)
(map double xs))
(double-all2 '(1 2 3)) ; '(2 4 6)
Notice that we had to define our doubling function. This is where anonymous functions come in. Their main use is for one time application for a simple functions in a higher order situation.
(define (double-all3 xs)
(map (lambda (x) (* 2 x)) xs))
(double-all3 '(1 2 3)) ; '(2 4 6)
Another lambda example #
Lets write a function that keeps the numbers 1 thru 100.
(define (keep-1-100 xs)
(filter (lambda (x) (and (> x 0) (< x 101))) xs))
(keep-1-100 '(1 -1 -10 50 99 100 101)) ; '(1 50 99 100)
Returning a function using a lambda #
; g(f(x))
(define (composer g f)
(lambda (x)
(g (f x))))
We can test out this function:
; using double function from earlier
(define double-add1 (composer add1 double))
(double-add1 10) ; 21
Expanding the keep-1-100
function
#
If we want to expand our 1-100 function to take any range, we can use lambdas. We can make a higher order function that creates a tester for a specific interval.
(define (interval-factory x y)
(lambda (z)
(and (< x z) (> y z))))
This returns a customized function based on the values we pass x
and y
.
We can define the 1-100 interval like so:
(define in-1-100 (interval-factory 1 100))
(in-1-100 50) ; #t
(in-1-100 150) ; #f
(filter in-1-100 '(-1 1 2 99 100 101)) ; '(2 99)
; another interval
(define in-50-1000 (interval-factory 50 1000))
(filter in-50-1000 '(-1 1 2 99 100 101)); '(99 100 101)
Functional closure #
Return an object that has copies of values in the current scope.
Graphical pseudo:
This is the idea of a closure.
In the definition of foo
, we are constructing an object that copies the current value of x
and y
.
If x
and y
change it would change the returned object, so we make a copy.
We did this earlier when we defined interval-factory
.
When we passed in certain values it copies those and returns an object with those values embedded.