This is a course web page of
David Casperson
 Associate Professor Computer Science University of Northern British Columbia

# CPSC 370: Functional and Logic Programming ( Fall 2011 Fall 2012 Fall 2013 Fall 2015 Fall 2016 Fall 2017 Fall 2018 Fall 2019 Fall 2022 )

## Homework now due

Questions 1–11 have been assigned due dates.

## Pending homework questions

1. Write a tail-recursive Scheme function `(exists predicate a-list)` that returns `#true` if and only if there is an element of `a-list` that satisfies `predicate`.

For instance, `(exists zero? '(1 2 3))` is `#false`.

2. Write a Haskell tail-recursive 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 tail-recursive.

3. Write a Haskell tail-recursive function that makes an in-order 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 tail-recursive.

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

2. [Optional]

Your assignment, should you choose to accept it, is to complete the code:

```        instance Foldable Tree where
…
```
3. What follows is a sequence of Prolog questions related to Peano arithmetic. Peano arithmetic constructs the non-negative integers from `zero` and a successor operation (`s`). For instance, 2 is represented as `s(s(zero))`.
4. 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.
5. 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.
6. 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.
7. 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.
1. The Prolog program:
```sumList([], 0).
sumList([X|Xs],NewSum) :- sumList(Xs, OldSum),
NewSum is X + OldSum.
```
works, but it is not tail-recursive. Rewrite `sumList/2` to call a helper function `sumList/3` that is tail-recursive.
2. The Prolog program `split_list(+List,-Left,-Right)` given by
```split_list(List,Left,Right) :-
split_list(List,List,Left,Right).

split_list([W|Walker], [_,_|Runner], [W|Left], Right) :-
split_list(Walker, Runner, Left, Right).
split_list(Walker, [], [], Walker).
split_list(Walker, [X], [], Walker).
```
splits a list into two pieces.
3. 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.
4. You may have noticed that the `split_list/4` predicate leaves extraneous choice points. Show how to use “`!`” to remove the extraneous choice points.
5. 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).
```    Fall 2017 2023-09 CPSC 370
References
Lecture Planning
Homework
Dates
Policies
Resources
David’s Schedule