This is a course web page of David Casperson 

Questions 1–11 have been assigned due dates.
(exists predicate alist)
that
returns #true
if and only if there is an element of
alist
that satisfies
predicate
.
For instance, (exists zero? '(1 2 3))
is #false
.
Write a Haskell tailrecursive function that counts the number of leaves in a
data Tree a =
Leaf a  Branch (Tree a)
(Tree a)
tree by using continuations.
Repeat using another strategy to make the function tailrecursive.
Write a Haskell tailrecursive function that makes an inorder list of the leaf values in a
data Tree a =
Leaf a  Branch (Tree a)
(Tree a)
tree by using continuations.
Repeat using another strategy to make the function tailrecursive.
However, this also requires a little theory. A monoid is a mathematical structure that has a binary associative operator and an identity element. The Haskell type class that captures this notion is Monoid.
A type function is Foldable if whenever you convert all
of the elements to some kind of monoid, you can fold them
together to get a monoid answer. That's quite abstract.
Here is an example. Suppose that we had written code so
that Tree
’s were an instance
of Foldable
.
Then we could use the Sum
monoid to count leaves as
follows:
import Data.Monoid(Sum) countLeaves :: Tree a > Int countLeaves tree = getSum (foldMap (\ x > Sum 1) tree)
In fact, for any foldable type the function length
automatically works (using essentiall the code above).
At first sight, this may seem harder than solving Question 13,
but note that we don’t need to worry about how to handle
the recursion. What is more, Question 14 becomes very simple:
treeToList :: Tree a > [a] treeToList tree = foldMap (\ x > [x]) tree
(This relies on the fact that []
is a monoid.)
Your assignment, should you choose to accept it, is to complete the code:
instance Foldable Tree where …
zero
and
a successor operation (s
). For instance, 2 is
represented as s(s(zero))
.
isPeano(+X)
that succeeds if X is
one of zero
, s(zero)
,
s(s(zero))
, s(s(s(zero)))
, …, and
for no other arguments.
peanoNumber(+X,Y)
that succeeds when X is
the peano version of the integer Y. Thus:
peanoNumber(s(s(zero)),Y)
should succeed
with Y=2
;
peanoNumber(s(s(zero)),3)
should fail.
peanoAdd(?X,?Y,?Z)
that succeeds
when the number represented by X plus the number represented by Y
equals Z. Use the facts that 0+Y=Y and (X+1)+Y=(Z+1) if and only
if X+Y=Z.
peanoMultiply(?X,?Y,?Z)
that succeeds
when the number represented by X times the number represented by Y
equals Z. Use the facts that (X+1)×Y = Y + X×Y.
sumList([], 0). sumList([XXs],NewSum) : sumList(Xs, OldSum), NewSum is X + OldSum.works, but it is not tailrecursive. Rewrite
sumList/2
to call a helper function sumList/3
that is
tailrecursive.
split_list(+List,Left,Right)
given by
split_list(List,Left,Right) : split_list(List,List,Left,Right). split_list([WWalker], [_,_Runner], [WLeft], Right) : split_list(Walker, Runner, Left, Right). split_list(Walker, [], [], Walker). split_list(Walker, [X], [], Walker).splits a list into two pieces.
guitracer.
and trace, split_list([1,2,3,4,5],L,R).
to watch how
this code works. Explain the code.
split_list/4
predicate leaves extraneous choice points. Show how to use
“!
” to remove the extraneous choice
points.
split_list
or code of your own design,
write Prolog code to merge sort a
list of numbers. (The recursive part of merge sort looks
something like:
m_sort(In,Out) : split_list(In, L, R), m_sort(L,L1), m_sort(R,R1), merge(L1,R1,Out).