The eopl library in racket exports keywords to help define datatypes.
Here is an example of a recursive type that attempts to create a list of numbers. A recursive type is a type that can contain an instance of itself- i.e: it recurses upon itself as a type.
The following is a recursive type for a Binary Tree structure.
(require eopl)
(define-datatype tree tree?
[leaf (key number?)]
[node (key number?) (left-parent tree?) (right-parent tree?)])An example usage of the datatype:
> (define node-1 (leaf 1))
> (define node-2 (leaf 2))
> (define root
(node 3 (list node-1 node-2)))
> root
(node 3 (leaf 1) (leaf 2))
Using the above-defined tree datatype, define the primitive map, reduce and filter functions to work over trees.
Write a function treeduce that takes a binary function f,
an initial value init and a binary tree tr, and reduces the tree of values to a single value.
The rules for the treeduce function are:
- The result of each pair of child nodes is computed and taken to the parent node
- The value of the (result of child nodes) is combined with the value of the parent node to give the final value of
that parent node
… And so on until the tree is reduced to one value.
(reduce + 0 (node 3 (list (leaf 1) (leaf 2)))) =
(reduce + 3 (node 3)) =
6
Write a function tree/map that takes an unary function f and a tree tr, and returns a new
tree by applying f to each node of tr. See the example below to understand how tree/map works:
(define incr
(lambda (x)
(x + 1)))
(tree/map incr (node 3 (list (leaf 1) (leaf 2)))) =
(node 4 (list (leaf 2) (leaf 3)))
Write a procedure path that takes an integer n and a binary search tree- in the given tree format- that contains the integer n, and returns a list of lefts and rights showing how to find the node containing n. If n is found at the root, it returns the empty list.
(Checking to see if the tree is a BST or if it contains n is not necessary)
> (define oneTree (node 14 (node 7 (leaf 5) (leaf 12)) (node 26 (leaf 17) (leaf 31))))
> (path 17 oneTree)
(right left)Instead of writing large blocks of code, the ideal style of functional programming involves writing a large function in terms of smaller, simpler functions, forcing you to break any problem down in terms of primitives and trying to connect primitives.
(Besides, the amount of bracket management involved in larger code blocks should convince you of the wisdom of keeping each racket function short.)
Reverse a list using reduce defined above.
;;; reverse : (listof value?) -> (listof value?)Hint: Use cons. See how varying the order in the binary operation of reduce affects your output.
Consider the procedurenumber-elements. This procedure shouldtake any list (v0 v1 v2...) and return the list
( (0 v0) (1 v1) (2 v2)...)
This function is defined in page 23 of the Essentials of Programming Languages textbook.
Write a procedure g such that number-elements could be defined as:
(define number-elements
(lambda (lst)
(if (null? lst)
'()
(g (list 0 (car lst))
(number-elements (cdr lst))))))A major principle of functional programming is immutability- that is, once you bind a value to a name, that value should not change. This
makes some imperative programming constructs like iterative loops impossible on the surface. While racket supports mutability through variable
assignment, you will not be allowed to use assignment in this question.
One of the simplest imperative programming algorithms a student learns are sorting algorithms, which usually involve iterative looping until a list is sorted.
Write the simple bubble-sort algorithm in Racket, as a function that takes a list ls and returns a sorted list.
Keeping in mind the “small function rule” mentioned above, write your bubble-sort function in terms of the swap function shown below:
(define swap
(lambda (ls)
;;; your code here
))
- Tangle all your code in a file named
fp.rkt - Submit only the org file on moodle as a
tarfile namedrollno_assignment-1.tar