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 ) Equations for `gcd′`

1. In Scheme, write a function that counts the `cons`es 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 `JoinList`s.
4. Create a `!!!` operator for `JoinList`s 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(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).
```

## 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.    Fall 2018 2023-06 Java
CPSC 200
CPSC 320
CPSC 370
References
Homework
Dates
Policies
Resources
David’s Schedule