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

CPSC 370: Functional and Logic Programming ( )

Equations for gcd

Equations for gcd

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

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

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

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

  1. 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.
  2. Write a Haskell function uncurry that takes a function of type a → b → c and returns a function of type (a,b) → c .
  3. Re-code the toList function from Question 12 by using continuations. If your original solution used continuations, find another tail-recursive approach.

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

  2. The Prolog program split_list(+List,-Left,-Right) given by
    split_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),

Older material

  1. What is the connection between “Haskell” and “Curry”ing?
  2. What should “Curry”ing really be called?
  1. See the handout on Currying for the following questions.
  2. Does not exist.
  3. Do Question 1 from the Handout.
  4. Do Question 2 from the Handout.
  1. Write a Scheme program to compute the function c(n), where c(n) is defined by
  2. 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.

Questions Still Pending

No questions are still pending.

Home page Semesters Site Map
go back Fall 2018 go forward
2023-06 other links

CPSC 200 [Other years]
CPSC 320 [Other years]
CPSC 370 [Other years]
David’s Schedule

UNBC Undergraduate Calendar