TEST
14
matricola: ______________________________
nome (solo se non si ricorda la matricola):
__________________________________
- Define a Scheme function taking as input a list ls and a
predicate P? on its elements, and which returns a list of two lists:
the list of the elements of ls satisfying P? and the list of the
elements of ls which do not satisfy P?.
Example: (F (list 1 2 3 4 5 6 7) even?) --> ((2
4 6) (1 3 5 7)
(define (partition ls P?)
(if (null? ls)
(list '() '())
(let ((first (car ls))
(res
(partition (cdr ls) P?)))
(if (P? first)
(list (cons first (car res)) (cadr res))
(list (car res) (cons first (cadr res)))))))
- Assume to have the data type of numeric labelled binary
tree in Scheme with the following constructors, predicates and
selectors: EmptyNBT, MkNBT, EmptyNBT?, LabelRootNBT, LeftNBT, RightNBT.
Define the function Insert
which, taken as input a number n and search tree t (i.e. a NBTree in
which the label of any node is always greater or equal to every
label of its left subtree and less than every label of its right
subtree) , returns another search tree, like t, but with a a new
leaf with label n.
(define (insert n t)
(cond ((EmptyNBT? t) (MkNBT n EmptyNBT EmptyNBT))
((<= n (LabelRoot t))
(MkNBT (LabelRoot t) (insert n (Left t)) (Right t)))
(else (MkNBT (LabelRoot t)
(Left t) (insert n (Right t))))))
- Define a Scheme Function CreateSumToFrom which
takes as input a unary function on integers and returns the binary
function that takes two numbers n and m, with n<=m, and returns
f(n)+f(n+1)+...f(m).
(define
(CreateSumToFrom f)
(lambda (n m)
(if (= n m)
(f n)
(+ (f n) ((CreateSumToFrom
f) (+ n 1) m)))))