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

Posted 2018-10-28

8. In Scheme, write a function that counts the conses in a Scheme expression. Make your function tail-recursive if possible.

9. Haskell has builtin functions for gcd and lcm. Nonetheless the goal of this exercise is to build your own gcd' function, using the definition above.

   Use Haskell guards to write the function.

10. In Haskell write a function isSorted :: Ord a => [a] -> Bool that returns true if and only if the list is sorted.

11. In Haskell write a function insert :: Ord a => a -> [a] -> [a] that inserts an element into an ordered list.

    Write a function insertionSort :: Ord a => [a] -> [a] that uses insert and foldr.

Posted 2018-11-23

12. Given the data type

    data JoinList a = Empty | Elt a 
                    | Join (JoinList a) (JoinList a)

    write the following functions:
    1. fromList:: [a] -> JoinList a
       that converts a list to a JoinList, preferably in a “balanced” way.
    2. toList:: JoinList a -> [a]
       that converts a JoinList to a list.
    3. [Optional] Create a Show for JoinList a so that you can print JoinLists.
    4. Create a !!! operator for JoinLists that finds the ith element of a JoinList.
13. Write a Haskell function uncurry that takes a function of type a → b → c and returns a function of type (a,b) → c .

14. Re-code the toList function from Question 12 by using continuations. If your original solution used continuations, find another tail-recursive approach.

Posted 2018-11-23

15. Write Prolog rules for a predicate nth so that nth(2,[a,b,c,d],c). returns true.

    Make your rules cope with as many situations as possible. For instance, it would be nice if your rules find both N=0 and N=2 when given the query. nth(N,[a,b,a,d],a). Comment on the combinations of variables that rules handle.

    N.B., this is builtin as predicate nth0, and there are answers on StackOverflow and elsewhere for how to do this. Write your own! (first.)

    N.B., you may want to check out the predicates var and ground.

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

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.

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

Posted 2018-09-10

1. What is the connection between “Haskell” and “Curry”ing?
2. What should “Curry”ing really be called?

2018-09-12

2. See the handout on Currying for the following questions.
3. Does not exist.
4. Do Question 1 from the Handout.
5. Do Question 2 from the Handout.

2018-09-21

6. Write a Scheme program to compute the function c(n), where c(n) is defined by
7. Write a Scheme program to compute the date of Easter. Use the algorithm from Lab 4 from my web-pages for CPSC 100 in Winter 2008. Look for modulo in the Racket Help desk for information on helpful arithmetic functions.