Test 1 Review A: Questions
Define the term purely functional language. That is, what property must a language have to be called purely functional?
Write a Haskell function twoToThe that takes an integer n
as a parameter and returns 2n, using no arithmetic
operations except multiplication.
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).
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.
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
Write a Haskell function threshold
that takes a function f and a number z and returns a
new function g for which
| f(x) | if x < z |
| 0 | otherwise |
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.)
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))².
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.
Define the term class as it relates to the Haskell programming language.
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
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
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.
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.
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.
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.
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).
Write a Haskell function sumLengths that takes a list of lists
and returns the sum of all the lists' lengths.
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.
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"]What is the type of the replicate function described in
the previous question? Use Haskell syntax to describe the
type.
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]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.
Define the term persistent data structure.
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.
Test 1 Review A: Solutions
A purely functional language must not have any constructs that change the state of the computer.
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
log2 1 = 0
log2 n = 1 + log2 (n `div` 2) -- can also write: 1 + log2 (div n 2)
fib n = helper 0 1 n
where helper a b 0 = b
helper a b i = helper b (a + b) (i - 1)
doubleFunc f = g where g x = 2 * f x -- one correct solution
doubleFunc f = \x -> 2 * f x -- another solution
doubleFunc = (.) (* 2) -- another solution
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
absSin = abs . sin
squareFn = (.) (** 2)
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.)
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
Eq a => a -> [a] -> Bool
applyIfDifferent :: Eq a => (a -> a -> b) -> a -> a -> b
data Suit = Clubs | Diamonds | Hearts | Spades
data Card = Normal Suit Integer | Joker
toList Null = []
toList (Node h t) = h : toList t
countZeroes [] = 0 -- one solution
countZeroes (0:xs) = 1 + countZeroes xs
countZeroes (_:xs) = countZeroes xs
countZeroes = length . filter (== 0) -- another solution
factorsFrom n i | i > n = []
| n `rem` i == 0 = i : factorsFrom n (i + 1)
| otherwise = factorsFrom n (i + 1)
everyOther [] = []
everyOther [a] = [a]
everyOther (x1:x2:xs) = x1 : everyOther xs
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
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
replicate 0 _ = []
replicate n v = v : replicate (n - 1) v
replicate :: Int -> a -> [a]
insert n [] = [n]
insert n (x:xs) | x <= n = x : insert n xs
| otherwise = n : x : xs
sumAbsolutes = sum . map abs
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.
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.]