Test 1 Review A

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25]

Problem R1a.1.

Define the term purely functional language. That is, what property must a language have to be called purely functional?

A purely functional language must not have any constructs that change the state of the computer.

Problem R1a.2.

Write a Haskell function twoToThe that takes an integer n as a parameter and returns 2ⁿ, using no arithmetic operations except multiplication.

twoToThe n = if n == 0 then 1 else 2 * twoToThe (n - 1)  -- one solution



twoToThe 0 = 1                               -- another solution

twoToThe n = 2 * twoToThe (n - 1)



twoToThe n = product (map (\n -> 2) [1..n])  -- another solution

Problem R1a.3.

Without using any sophisticated functions beyond div, which takes two integer arguments and returns the result of integer division between them, write a Haskell function log2 that takes a parameter n and returns the number of times you can divide n by 2 before reaching 1. For example, log2 25 should return 4, since 25 is halved four times before reaching 1 (first to 12, then 6, then 3, then 1).

log2 1 = 0

log2 n = 1 + log2 (n `div` 2)   -- can also write: 1 + log2 (div n 2)

Problem R1a.4.

Recall that the Fibonacci numbers are 1, 1, 2, 3, 5, 8, et cetera, where each Fibonacci is the sum of the preceding two. Write a Haskell function fib that takes an integer parameter n and computes the nth Fibonacci number in O(n) time. For example, fib 5 should return 8.

fib n = helper 0 1 n

  where helper a b 0 = b

        helper a b i = helper b (a + b) (i - 1)

Problem R1a.5.

Write a Haskell function doubleFunc which takes as its parameter a function f from integers to integers and returns a function from integers to integers which is always twice f. For example, with the definitions below using your definition of doubleFunc, the expression fd 3 should return 2 (3 + 5) = 16 and gd 10 should return 2 (3 ⋅ 10) = 60.

f x = x + 5 g x = 3 * x fd = doubleFunc f gd = doubleFunc g

doubleFunc f = g where g x = 2 * f x         -- one correct solution



doubleFunc f = \x -> 2 * f x                 -- another solution



doubleFunc = (.) (* 2)                       -- another solution

Problem R1a.6.

Write a Haskell function threshold that takes a function f and a number z and returns a new function g for which

g(x) = {

`f`(`x`)	if `x` < `z`
0	otherwise

threshold f z = (\x -> if x < z then f x else 0)  -- one solution



threshold f z x = if x < z then f x else 0        -- another solution



threshold f z = g                             -- yet another solution

    where g x | x < z     = f x

              | otherwise = 0

Problem R1a.7.

Without using any identifiers to represent parameters, define a function absSin that takes a number representing radians and returns the absolute value of that number's sine. (Haskell has built-in functions abs and sin.)

absSin = abs . sin

Problem R1a.8.

Without using any identifiers to represent parameters, define a function squareFn that takes a function f of type Double -> Double and returns a new function g where g(x) = (f(x))².

squareFn = (.) (** 2)

Problem R1a.9.

Many languages (such as Java and Haskell) do static type checking, while others (such as Python and JavaScript) use dynamic type checking.

a. Name and explain an advantage of static type checking over dynamic type checking.

b. Name and explain an advantage of dynamic type checking over static type checking.

a. Programmer errors are detected at compile-time, so that debugging happens more reliably and faster. (Another answer: Program execution is faster, as type-checking for each operation is expensive.)

b. It allows more flexibility to the programmer, so that variables can mean different things at different times. (Another answer: The code tends to be simpler, as it does not require code to associate types with variables.)

Problem R1a.10.

Define the term class as it relates to the Haskell programming language.

A class is a set of functions that any type that is a member (instance) of the class must define. For example, we might define the Measurable class:

class Measurable a where size :: a -> Integer

Now, if we have a type that we want to include in this class, we can declare it as an instance. The following declares lists of any type of data to be in the Measurable class.

instance Measurable [a] where size [] = 0 size (x:xs) = 1 + size xs

Problem R1a.11.

What is the most general possible type for the following Haskell function? Describe the type using Haskell syntax.

member _ [] = False

member query (x:xs) = if x == query then True else member query xs

Eq a => a -> [a] -> Bool

Problem R1a.12.

Using Haskell syntax for writing types, give the most general type for the following function.

applyIfDifferent f x y = if x == y then f x x else f x y

applyIfDifferent :: Eq a => (a -> a -> b) -> a -> a -> b

Problem R1a.13.

Give a suitable definition of a type for representing cards of a deck, including normal cards with a suit (clubs, diamonds, hearts, spades) and a rank (1…13) as well as jokers.

data Suit = Clubs | Diamonds | Hearts | Spades



data Card = Normal Suit Integer | Joker

Problem R1a.14.

Suppose we have the following data definition to represent a node in a list. Each node holds both a value and a reference to the first node following it in the list.

data ListNode a = Null | Node a (ListNode a)

Write a function toList that takes a node as defined above and returns a normal list of all the data in that node and succeeding nodes.

toList Null       = []

toList (Node h t) = h : toList t

Problem R1a.15.

Write a Haskell function countZeroes that takes a list of integers as a parameter and returns the number of zeroes contained in the list. For example, if I called countZeroes [5,0,0,8,0], it should return 3, since the list contains three zeroes.

countZeroes [] = 0                       -- one solution

countZeroes (0:xs) = 1 + countZeroes xs

countZeroes (_:xs) = countZeroes xs



countZeroes = length . filter (== 0)     -- another solution

Problem R1a.16.

Write a Haskell function factorsFrom that takes two integers n and i and returns a list of all the factors of n that are at least i.

factorsFrom n i | i > n          = []

                | n `rem` i == 0 = i : factorsFrom n (i + 1)

                | otherwise      = factorsFrom n (i + 1)

Problem R1a.17.

Write a Haskell function everyOther which takes a list and returns a list containing every other element of it. For example, everyOther [1..10] should return the list [1,3,5,7,9]. Your function should be able to work for lists of any length (whether even or odd).

everyOther [] = []

everyOther [a] = [a]

everyOther (x1:x2:xs) = x1 : everyOther xs

Problem R1a.18.

Write a Haskell function sumLengths that takes a list of lists and returns the sum of all the lists' lengths.

sumLengths [] = 0                            -- one solution

sumLengths (lst:lsts) = length lst + sumLengths lsts



sumLengths lists = sum (map length lists)    -- another solution



sumLengths = sum . map length                -- another solution

Problem R1a.19.

Write a Haskell function select, which takes a list indices of integers (which you may assume is in increasing order) and another list values, and it returns the items of values at the indices mentioned in indices. For example, select [1,2,4] [10..20] would return [11,12,14], since 11 is at position 1 in the list [10..20] (we start numbering positions from 0), 12 at position 2, and 14 at position 4. Your function should be able to work in O(n) time, where n is the length of values.

selectSub [] _ _ = []

selectSub (i:is) (v:vs) pos =

    if pos == i then v : selectSub is vs (pos + 1)

                else selectSub (i : is) vs (pos + 1)



select indices data = selectSub indices data 0

Problem R1a.20.

Write a Haskell function replicate that takes an integer n and a value v and returns a list containing n copies of v. (This function is actually pre-defined in the Prelude, but of course you shouldn't use the pre-defined function to define this one.) For example:

replicate 3 "a" should return ["a", "a", "a"]

replicate 0 _ = []

replicate n v = v : replicate (n - 1) v

Problem R1a.21.

What is the type of the replicate function described in the previous question? Use Haskell syntax to describe the type.

replicate :: Int -> a -> [a]

Problem R1a.22.

Write a Haskell function insert that takes an integer n and a list lst of integers assumed to be in increasing order, and then returns a list containing the same elements of lst but with n inserted so that the integers are still ascending. For example:

insert 4 [2,3,5] should return [2,3,4,5]

insert n [] = [n]

insert n (x:xs) | x <= n     = x : insert n xs

                | otherwise  = n : x : xs

Problem R1a.23.

Without using any identifiers to represent parameters, write a Haskell function sumAbsolutes that takes a list of numbers and returns the sum of the absolute values of those numbers.

sumAbsolutes = sum . map abs

Problem R1a.24.

Define the term persistent data structure.

A persistent data structure is a data structure where no operations modify the existing structure, although there may be operations that create new structures based on the existing structure. Logically, these newly created structures would be slightly mutated copies of the original.

Problem R1a.25.

Explain why it is a poor idea to use a Haskell list to represent the Queue abstract data type, where the front of the queue is the same as the front of the list.

Enqueueing data at the tail of a list takes O(n) time, which is much more than the O(1) time we would expect from an efficient queue implementation. [Technically, since Haskell uses lazy lists, enqueueing takes O(1) time, and it is dequeueing that must disentangle all the lazy conses, taking O(n) time.]