===== Lab 4: Higher-order functions and tree recursion =====
**Exercise 1:** Write a function ''(permutations lst)'' taking a list ''lst'' and returning all its permutations. E.g. ''(permutations '(1 2 3)) => ((1 2 3) (2 1 3) (2 3 1) (1 3 2) (3 1 2) (3 2 1))''.
//Hint:// Suppose that we have all permutations of a list of length $n$ and we want to build all permutations of its extension by an element. To do that it suffices to take the element and interleave it in all possible ways into all the permutations of length $n$. For instance, ''((2 3) (3 2))'' are all permutations of the list ''(2 3)''. If we want to compute all permutations of ''(1 2 3)'', we take each permutation of length 2 and interleave the element ''1'' into it as follows:
(2 3) => ((1 2 3) (2 1 3) (2 3 1))
(3 2) => ((1 3 2) (3 1 2) (3 2 1))
Appending all these lists gives us the desired permutations of ''(1 2 3)''.
Write first a function ''interleave'' taking an element, a list and returning all possible ways of inserting the element into the list.
Using this function, devise the function ''permutations'' using the recursion on the length of ''lst''.
++++ Solution |
(define (interleave el)
(lambda (lst)
(if (null? lst)
(list (list el)) ; there is only a single way one can insert el into '()
(cons (cons el lst) ; otherwise one possibility is to prepend el to lst
(map ((curry cons) (car lst))
((interleave el) (cdr lst))))))) ; or take all possible insertions of el into (cdr lst)
(define (permutations lst)
(if (null? lst)
'(())
(apply append
(map (interleave (car lst)) (permutations (cdr lst)))))) ; into each permutation of (cdr lst) interleave (car lst)
; and append the results
++++
**Exercise 2:** Binary decision trees are tree representing Boolean functions, i.e., functions from $\{0,1\}^n$ to $\{0,1\}$. Let $f(x_1,\ldots,x_n)$ be a Boolean function. The corresponding binary decision tree is created as follows:
- Each input variable $x_i$ induces the $i$th-level in the tree whose nodes are labelled by $x_i$.
- Leaves are elements from $\{0,1\}$.
Each path from the root to a leaf encodes an evaluation of input variables. If the path in an internal node $x_i$ goes to the left, the variable $x_i$ is evaluated by $0$. If to the right, it is evaluated by $1$. The leaf in the path represents the value $f(x_1,\ldots,x_n)$ for the evaluation defined by the path.
Example of a Boolean function and its binary decision tree:
{{ :courses:fup:tutorials:bdd.png?400 |}}
We will represent such binary tree in Scheme by nested lists. The internal nodes are of the form ''( )''. For instance, the above tree is represented as follows:
(define bool-tree '(x1 (x2 (x3 1 0) (x3 0 1)) (x2 (x3 0 0) (x3 1 1))))
#| Alternatively, we can use a struct here, which generates a constructor `bintree`, a predicate `bintree?`, and accessors `bintree-label`, `bintree-left` and `bintree-right` automatically
(struct bintree (label left right))
(define bool-tree
(bintree
'x1
(bintree
'x2
(bintree 'x3 1 0)
(bintree 'x3 0 1))
(bintree
'x2
(bintree 'x3 0 0)
(bintree 'x3 1 1))))
|#
Your task is to write two functions. The first one ''(evaluate tree vals)'' takes a binary decision tree ''tree'' representing a Boolean function $f(x_1,\ldots,x_n)$, a list ''vals'' of values of variables $x_1,\ldots,x_n$ and returns $f(x_1,\ldots,x_n)$. E.g.
(evaluate bool-tree '(1 0 1)) => 0
(evaluate bool-tree '(0 1 1)) => 1
The second function ''(satisficing-evaluations tree)'' taking a binary decision tree ''tree'' representing a Boolean function $f(x_1,\ldots,x_n)$ and returning all its satisficing evaluations, i.e., those for which $f(x_1,\ldots,x_n)=1$. E.g.
(satisficing-evaluations bool-tree) =>
(((x1 0) (x2 0) (x3 0)) ((x1 0) (x2 1) (x3 1)) ((x1 1) (x2 1) (x3 0)) ((x1 1) (x2 1) (x3 1)))
Before we start to code the functions itself, we define a couple of helper functions accessing the members of a node.
(define (variable tree) (car tree))
(define (left-subtree tree) (cadr tree))
(define (right-subtree tree) (caddr tree))
Such functions are not necessary but it is a good practice to define them for the following reasons:
- Your code is more readable. E.g. if I write ''(iter (right-subtree tr) ...'', then it is clear that I iterate over the right subtree. On the other hand, one has to remember the precise structure of the node to understand ''(iter (caddr tr) ...''.
- Such helper functions erect so-called abstraction barriers between your code and the data representation. If you decide for some reason to change your representation (e.g, to change the structure of nodes to ''( )''), it suffices to recode only helpers functions. The rest of your code stays untouched unlike the case when you don't use them.
We devise two versions of ''evaluate''. The first is the recursive function consuming consecutively values of $x_1,\ldots,x_n$ and based on its value recursively evaluate either left or right subtree. Once all the values are consumed, we should be in a leaf specifying the value of $f(x_1,\ldots,x_n)$.
++++ 1st evaluate |
(define (evaluate tree vals)
(cond
([null? vals] tree) ; the leaf is the resulting value
([= (car vals) 0] (evaluate (left-subtree tree) (cdr vals))) ; if the variable value is 0, go to the left
(else (evaluate (right-subtree tree) (cdr vals))))) ; otherwise go to the right
#| Alternative with `match`
(require racket/match)
(define (evaluate tree decs)
(match decs
['() tree]
[`(0 . ,tail) (evaluate (bintree-left tree) tail)]
[`(1 . ,tail) (evaluate (bintree-right tree) tail)]))
|#
++++
The second version uses higher-order functions. It takes the list of values of $x_1,\ldots,x_n$ and converts it into the list of functions ''left-subtree'', ''right-subtree'' corresponding to the path defined by ''vals''. Finally, it applies their composition to ''tree''.
++++ 2nd evaluate |
(define (evaluate2 tree vals)
(define (left-right v) ; define function 0 -> left-subtree, 1 -> right-subtree
(if (= v 0) left-subtree right-subtree))
((apply compose (map left-right (reverse vals))) tree)) ; map it over vals, compose and apply to tree
++++
The function ''satisficing-evaluations'' is a recursive function using an accumulator ''ev'' keeping partial evaluation as we traverse the tree.
It recursively finds all satisficing evaluations of the left and right subtree, extends them by $0$ (resp. $1$) if they come from left (resp. right), and append them together.
++++ Solution |
(define (satisficing-evaluations tree)
(define (make-assignment var val) (list var val)) ; a helper function creating an assignment
(define (iter tr ev)
(if (number? tr) ; are we in a leaf?
(if (= tr 1) (list (reverse ev)) '()) ; if yes and the resulting value is 1 return that evaluation, otherwise discard it
(append (iter (left-subtree tr) (cons (make-assignment (variable tr) 0) ev)) ; if not, extend the partial evaluation ev
(iter (right-subtree tr) (cons (make-assignment (variable tr) 1) ev))))) ; recursively collects satisficing evaluations for
; left and right subtree and append
(iter tree '()))
#| Alternative with `match`
(require racket/match)
(define (satisficing-evaluations tree [rev-path '()])
(match tree
[0 '()]
[1 (list (reverse rev-path))]
[(bintree lbl left right)
(let [(left-paths
(satisficing-evaluations
left
(cons (list lbl 0)
rev-path)))
(right-paths
(satisficing-evaluations
right
(cons (list lbl 1)
rev-path)))]
(append left-paths right-paths))]))
|#
++++
**Task 1:** Write a function ''(sub-seq lst)'' taking a list ''lst'' and returning a list of all its sublists/subsequences. E.g.
(sub-seq '(1 2 3)) =>
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
//Hint:// Code it as a recursive function using the following facts. 1) There is only a single subsequence of the empty list, namely the empty list. 2) Subsequences of $(x_1,x_2,\ldots,x_n)$ are just subsequences of $(x_2,\ldots,x_n)$ together with subsequences starting with $x_1$ and following by a subsequence of $(x_2,\ldots,x_n)$.
++++ Solution |
(define (sub-seq lst)
(if (null? lst)
'(())
(let ([el (car lst)]
[rest-sub-seq (sub-seq (cdr lst))])
(append rest-sub-seq
(map ((curry cons) el) rest-sub-seq)))))
++++
**Task 2:** Consider a binary tree representing a tournament. Each internal node corresponds to a match. Its structure is ''( )''. Leafs are of the form ''()''. E.g.
(define tournament '(F (D (A (A) (B)) (D (C) (D))) (F (F (E) (F)) (G (G) (H)))))
represents the following tree:
F
/ \
/ \
/ \
/ \
/ \
D F
/ \ / \
/ \ / \
A D F G
/ \ / \ / \ / \
A B C D E F G H
Write a function ''(beaten-teams tree)'' taking a binary tournament tree and outputting the list of beaten teams by the winner. E.g. ''(beaten-teams tournament) => (D G E)''.
//Hint:// Code it as a recursive function starting in the root defining the winner of the tournament. Then follow the path labelled by the winner and collects the beaten teams along the path to an accumulator. Once you are in a leaf return the accumulator.
++++ Solution |
(define (beaten-teams tree)
(define (winner tr) (car tr))
(define (is-leaf? tr) (= (length tr) 1))
(define (left-subtree tr) (cadr tr))
(define (right-subtree tr) (caddr tr))
(define (iter tr acc)
(cond
([is-leaf? tr] acc)
([eqv? (winner (left-subtree tr)) (winner tree)]
(iter (left-subtree tr)
(cons (winner (right-subtree tr)) acc)))
(else
(iter (right-subtree tr)
(cons (winner (left-subtree tr)) acc)))))
(iter tree '()))
++++