Some Final Practice Problems

Practice Go Questions

  1. Using English plus simple code examples, explain the difference between arrays and slices in Go.

  2. Using English plus a simple code example, give a major reason why Go does not let you pass a slice to a function that expects an array.

  3. Write a function called vc_count(s string) that returns the number of vowels and consonants in s.

    A vowel is defined to be one of these lowercase letters: a, e, i, o, u, y. A consonant is defined to be any character that is not a vowel, and also the letter y. Thus y should be counted as both a vowel and a consonant.

    Also, you must use a ranged for-loop (in a sensible way) in your solution.

    Your function must work with code like this:

    v, c := vc_count("yay")
fmt.Println(v, c)

  4. Write a goroutine called char_gen(s string, out chan rune) that returns the characters of s one at a time on channel out. Use the built-in function close to close out when all the characters have been sent.

    Demonstrate how to use char_gen by writing a main function that uses it to print out an entire string.

  5. Answer all the following questions with Go code.

    1. Write a function called add(x, y) that returns the sum of two ints, e.g.:

      fmt.Println(add(3, 5));  // 8

  1. Write a function called c_add that is a curried version of add, e.g.:

    add3 := c_add(3)
fmt.Println(add3(5))      // 8

fmt.Println(c_add(2)(4))  // 6

  2. Write a function called curry(f) that returns a curried version of f. Assume that f is a (non-curried) function that takes two ints as input and returns an int.

    It can be used like this:

    curr_add := curry(add)  // add is the regular non-curried add function
add2 := curr_add(2)
fmt.Println(add2(6))    // 8

  1. a) Write a function called negpos(s) that takes a slice of ints as input, and returns two new slices, named neg and pos, where neg contains all the numbers in s that are less than 0, and pos contains all the numbers in s that are greater than, or equal to, 0. For example:

    s := []int{6, -2, 0, 2, -6, -4, 3}
neg, pos := negpos(s)
fmt.Println(neg)   // {-2, -6, -4}
fmt.Println(pos)   // {6, 0, 2, 3}

    Use features of Go to make negpos as short and clear as possible.

    b) To help test your negpos function, write a function called all(s, pred) where:

    • s is a slice of int values
    • pred is a function that takes one int as input, and returns a bool

all(s, pred) returns true if every int in s is true for pred, and false otherwise (i.e. it returns false if s contains 1, or more, int` values that cause ``pred to return false).

c) Write a single Go statement of the form all(s, pred) that returns true just when every element in s is less than 0, and false otherwise.

Solutions.

Practice Scheme Programming Questions

In the following questions, pred is a predicate, i.e. a function that takes one input and returns either #t or #f. If (pred x) is #t, then we say that x satsifies pred.

  1. Implement a function called (some? pred lst) that returns #t if 1, or more, elements of lst satisfy pred, and #f otherwise. Implement this two different ways:
    1. Recursively using basic Scheme functions.
    2. Using a single call to the standard Scheme fold function (and no recursion).
  2. Implement a function called (all? pred lst) that returns #t if all the elements of lst satisfy pred, and #f otherwise. Implement this three different ways:
    1. Recursively using basic Scheme functions.
    2. Using a single call to the standard Scheme fold function (and no recursion).
    3. Using the some? function from the previous question, and no recursion, and no use of fold.
  3. Implement a function called (none? pred lst) that returns #t if 0 elements of lst satisfy pred, and #f otherwise. Implement this three different ways:
    1. Recursively using basic Scheme functions.
    2. Using a single call to the standard Scheme fold function (and no recursion).
    3. Using the some? and/or all? functions from the previous question, and no recursion, and no use of fold.
  4. Implement a function called (sat-n? pred lst) that returns #t if exactly n elements of lst satisfy pred, and #f otherwise.
  5. Implement a function called (sat-count pred lst) that returns the total number of elements of lst that satisfy pred.
  6. Re-implement some?, all?, none?, and sat-n? using a single call to sat-count for each.
  7. Write a function called (negate pred) that returns a new predicate that is the negation of pred. For example (negate zero?) returns a new function that returns #t when it is passed a non-zero input, and #f if it is passed 0. The function (zero? n) is built-in and returns #t just when n is 0.
  8. Write a function called (conjoin pred1 pred2) that returns a new predicate that behaves the same as pred1 and pred2 and-ed together.
  9. Write a function called (disjoin pred1 pred2) that returns a new predicate that behaves the same as pred1 and pred2 or-ed together.

Solutions.

Practice Haskell Programming Questions

  1. Write a function called isdigit that tests if a character is one of the digits '0', '1', …, '9'. It has this signature:

    isdigit :: Char -> Bool

  2. Write a function called isletter that tests if a character is one of the 26 lowercase letters 'a', 'b', …, 'z', or one of the 26 uppercase letters 'A', 'B', …, 'Z'. It has this signature:

    isletter :: Char -> Bool

  3. The following functions each take a predicate function and a list as input, and remove certain items from the list based on the predicate function. They all have this signature:

    (a -> Bool) -> [a] -> [a]
    1. ltrim removes all items from the start of the list that satisfy the predicate function.
    2. rtrim removes all items from the end of the list that satisfy the predicate function.
    3. trim removes all items from both the start and end of the list that satisfy the predicate function.

  4. Write the following two functions:

    1. lpad c n lst returns a new list equal to lst but with n copies of c on the left side. Write the most general type signature for it.

      For example:

      > lpad '*' 5 "apple"
"*****apple"

    2. rpad c n lst returns a new list equal to lst but with n copies of c on the right side. Write the most general type signature for it.

      For example:

      > lpad '*' 5 "apple"
"apple*****"

Solutions.

Prolog Practice Questions

In the follow Prolog questions, your functions only need to work correctly for the first solution that they return. It’s okay if they don’t work perfectly after the first correct solution is returned.

Of course, it would be best to have your functions work perfectly in all cases, but that may require using advanced features such as cuts, that we didn’t cover in this course.

  1. Write a function called is_sorted(Lst) that succeeds if Lst is a list of numbers in ascending sorted order, and fails otherwise. For example:

    ?- is_sorted([]).
true.

?- is_sorted([6]).
true .

?- is_sorted([6, 9]).
true .

?- is_sorted([4, 4, 4]).
true .

?- is_sorted([1, 2, 3, 5, 4, 6]).
false.

    Your implementation should be relatively efficient and use basic Prolog features (don’t use sorting in your answer).

  2. Write a function called qsort(Lst, Sorted) that sorts the list of numbers Lst, putting the result in Sorted. For example:

    ?- qsort([], Sorted).
Sorted = [].

?- qsort([4], Sorted).
Sorted = [4] .

?- qsort([4, 5], Sorted).
Sorted = [4, 5] .

?- qsort([5, 4], Sorted).
Sorted = [4, 5] .

?- qsort([1, 5, 4], Sorted).
Sorted = [1, 5, 4] ..

?- qsort([5, 1, 9, 3, 2, 0, 2, 0, 0], Sorted).
Sorted = [0, 0, 0, 1, 2, 2, 3, 5, 9] .

    qsort should also be able to test if a list is sorted, e.g:

    ?- qsort([5,6,7], [5,6,7]).
true .

?- qsort([5,6,7], [5,7,6]).
false.

    Note that qsort only needs to follow the basic outline of quicksort. It’s okay if it is inefficient when, say, combining the sorted sub-lists.

Solutions.