1. Name three different ways that the following code is “imperative.”
1) It mutates state, for example: myarray[firstPos] = myarray[otherPos]
2) To hold data it uses an array “myarray,” which is not a recursive data structure. 3) To accomplish repetitive computation, it iterates with a for loop.
2. Consider the following function definition:
(define (fib count a b)
(if (= count 0)
a
(fib (- count 1) b (+ a b))))
Trace the evaluation of (fibonacci 4 0 1). (fibonacci 4 0 1)
(fibonacci 3 1 1)
(fibonacci 2 1 2)
(fibonacci 1 2 3) (fibonacci 0 3 5) 3
Is this function tail recursive or non-tail recursive?
It is tail recursive. You can tell, because there are no operations from earlier recursive calls that are waiting for later recursive calls to return in order to complete their evaluation.
Rewrite tail recursively using pattern matching in Haskell. Include the type signature, assuming a, b, and count will only ever be Ints.
fibonacci :: Int -> Int -> Int -> Int
fibonacci 0 a _ = a
fibonacci count a b = fibonacci (count – 1) b $! (a + b)
3. Write a recursion function in Racket called factors that takes some number n as an argument, and returns a list of all the factors of that number. You might want to achieve this with a nested definition, or with two separate definitions (I did mine with two separate functions).
(define (factors n)
(my-factors n 1))
(define (my-factors n t)
(if (= (+ n 1) t)
‘()
(if (= 0 (modulo n t))
(cons t (my-factors n (+ t 1)))
(my-factors n (+ t 1)))))
4. Why the difference?
Haskell evaluates lazily, whereas Racket evaluates eagerly. That means that, for the Racket, even though y will not used in the body of foo because x is 10, nonetheless the argument (car ‘()) will still be evaluated, and the expression will throw the error because you can’t take the head of an empty list (in Racket or in Haskell). In the Haskell, the argument (head []) will remain unevaluated, and because it is not used in the body of foo (because x is 10), it will never be evaluated.
5.
1. fallsBetween low high item = low < item && high > item
2. allBetween _ _ [] = [] allBetween low high (x:xs)
| fallsBetween low high x = x : allBetween low high xs | otherwise = allBetween low high xs
3. allBetween low high = filter (fallsBetween low high)
You can also write: allBetween low high ls = filter (fallsBetween low high) ls 4. allBetween low high ls = [x | x <- ls, fallsBetween low high x]
5. This type signature states that this function takes items from the Ord typeclass, which means that the items are any types orderable using the < or > operator. The function takes two arguments of this type, low and high, and a list of things of that type, and returns, overall, a list of things of that same orderable type, namely the items in the input list that are between the low and high arguments.
6. Eager Evaluation
false
Lazy Evaluation
false
“true” means choose the first of two arguments
(¦Ën.(n true) (¦Ën.¦Ës.((s false) n) ¦Ët.((t false) ¦Ëx.x)))
(¦Ën.(n true) ¦Ës.((s false) ¦Ët.((t false) ¦Ëx.x)))
(¦Ës.((s false) ¦Ët.((t false) ¦Ëx.x)) true)
((true false) ¦Ët.((t false) ¦Ëx.x))
(¦Ën.(n true) (¦Ën.¦Ës.((s false) n) (¦Ëm.¦Ët.((t false) m) ¦Ëx.x)))
((¦Ën.¦Ës.((s false) n) (¦Ëm.¦Ët.((t false) m) ¦Ëx.x)) true)
(¦Ës.((s false) (¦Ëm.¦Ët.((t false) m) ¦Ëx.x)) true)
((true false) (¦Ëm.¦Ët.((t false) m) ¦Ëx.x)) “true” means choose the first of two arguments