Last modified: 2017-12-01
This is a course web page of
David Casperson
Associate Professor
Computer Science
University of Northern British Columbia

CPSC 370: Functional and Logic Programming ( )

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).
        
Home page Semesters Site Map
go back Fall 2017 go forward
2018-06 other links

CPSC 370 [Other years]
References
Homework
Dates
Policies
Resources
David’s Schedule

UNBC Undergraduate Calendar