#!r6rs
;; a Scheme exercise, MPradella MMXII
(import (rnrs))
;; --- Q
;; Part 1) 'exists' is a standard function defined in the list library that takes
;; a predicate P and a list L, and returns true iff there exists an element t in L such that P(t).
;; 1/a) Write a pure functional implementation of exists
;; --- A
(define (my-exists P L)
(not (null? (filter P L))))
;; --- Q
;; 1/b) Does the code just written stop at the first element found for which P holds? If not, optimize it.
;; --- A
(define (my-exists-opt P L)
(call/cc (lambda (exit)
(not (null? (filter
(lambda (t)
(if (P t)
(exit #t)
#f))
L))))))
;; --- Q
;; Part 2) Consider a tree whose nodes are stored as lists, and the first
;; element is the value stored at that node, while the other elements are subtrees.
;; an example tree
(define a-tree '(root
(a
(b 1 2 3)
(c 2))
(f
(g x y))))
;; 2/a) define a possibly concise function to find an element in the tree
;; --- A
(define (find-tree tree x)
(if (not (list? tree))
(eqv? x tree)
(exists (lambda (y) (find-tree y x)) tree)))
;; --- Q
;; 2/b) define the same function in Prolog
;; --- A
;; we suppose that trees are stored in the same way as in Scheme
;; e.g. [root,[a,[b,1,2,3],[c,2],[f,[g,x,y]]]]
;; findlist([],_) :- fail.
;; findlist([X|L],X).
;; findlist([Y|L],X) :- findlist(Y,X) ; findlist(L,X).
;; --- A
;; a more natural way of representing such trees is by using terms
;; e.g.
;; root(a,b(1,2,3),c(2),f(g(x,y)))
;; here is the solution for this case:
;; findtreel([],_) :- fail.
;; findtreel([Y|_],X) :- findtree(Y,X).
;; findtreel([_|L],X) :- findtreel(L,X).
;; findtree(X,X).
;; findtree(T,X) :- T =.. [X|_].
;; findtree(T,X) :- T =.. [_|L], findtreel(L,X).