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

Pending homework questions

2017-11-03

12. 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.

13. 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.

14. 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.

2017-11-03

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

16. [Optional]

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

            instance Foldable Tree where
            …
          

17. 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)).
18. 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.
19. 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.
20. 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.
21. 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.

2017-12-01

22. 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.
23. 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.
24. 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.
25. You may have noticed that the split_list/4 predicate leaves extraneous choice points. Show how to use “!” to remove the extraneous choice points.
26. 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).