Homework now due
Questions 1–11
have been assigned due dates.
Pending homework questions
20171103

Write a tailrecursive Scheme
function
(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.
20171103

Good Haskell programmers
try to avoid writing recursive programs like those in
Questions 13 and 14 by exploiting more general patterns.
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.)

[Optional]
Your assignment, should you choose to accept it, is to
complete the code:
instance Foldable Tree where
…

What follows is a sequence of Prolog
questions related to Peano arithmetic. Peano arithmetic
constructs the nonnegative integers from
zero and
a successor operation (s ). For instance, 2 is
represented as s(s(zero)) .

Write a predicate
isPeano(+X) that succeeds if X is
one of zero , s(zero) ,
s(s(zero)) , s(s(s(zero))) , …, and
for no other arguments.

Write a predicate
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.

Write a predicate
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.

Write a predicate
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.
20171201
 The Prolog program:
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.

The Prolog program
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.

What happens with odd sized lists? Use
guitracer.
and trace, split_list([1,2,3,4,5],L,R). to watch how
this code works. Explain the code.
 You may have noticed that the
split_list/4
predicate leaves extraneous choice points. Show how to use
“! ” to remove the extraneous choice
points.

Using
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).



CPSC 370
[Other years]
 References
 Homework
 Dates
 Policies
 Resources

David’s Schedule
 UNBC Undergraduate Calendar
