[SOLVED] CS Haskell compiler Lambda Calculus interpreter Practice Midterm

Practice Midterm
Started: Mar 13 at 6:29pm
QUIZ INSTRUCTIONS
The Midterm will be closed notes, no interpreters/compilers, and no Web searching.
You will have 65 minutes to complete the real test unless you have SDS accommodations for more time. This practice test is about twice as long as the real midterm will be, to give you more practice. The answer key to this practice exam is here: Sprign2021PracticeMidtermAnswers.pdf
Question 1 1 pts
Name three different ways that the following code is imperative.
myarray = [3,4,2,6,1]
def swap(firstPos, otherPos):
temp = myarray[firstPos]
myarray[firstPos] = myarray[otherPos]
myarray[otherPos] = temp
def bubbleSort(arr):
for i in range(len(arr)):
for j in range(len(arr)-1):
if arr[j] > arr[j+1]:
swap(j, j+1)
bubbleSort(myarray)

Edit View Insert Format Tools Table 12pt Paragraph
p
0 words

print (myarray)
Question 2 1 pts
Consider the following function definition:

1. Trace the evaluation of (fibonacci 4 0 1).
2. Is this function tail recursive or non-tail recursive, and how can you tell?
3. Write the same function tail recursively using pattern matching in Haskell. Hint: use $!. Include the type signature, assuming that the arguments count, a and b will only ever be Ints.
Edit View Insert Format Tools Table 12pt Paragraph
p
0 words

(define (fibonacci count a b)
(if (= count 0)
a
(fibonacci (- count 1) b (+ a b))))

Question 3 1 pts
Write a recursive 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, where your other definition takes a second argument.
(define (factors n)
(your code goes here)
> (factors 6) > (1 2 3 6)
Edit View Insert Format Tools Table 12pt Paragraph

p 0 words

Question 4 1 pts
In Haskell, this code
returns 10. But in Racket, the equivalent code returns a contract violation error:
foo :: (Ord p, Num p) => p -> p -> p
foo x y = if (x > 0) then x else y
foo 10 (head [])
(define (foo x y)
(if (> x 0)
x y)
(foo 10 (car ()))
Why the difference?
Edit View Insert Format Tools Table 12pt Paragraph

p 0 words
Question 5 1 pts
This Haskell question has five parts: be sure to answer all of them.
1. Write a predicate function called fallsBetween, which should take three arguments: low, high, and an item. The function should return true if item is between low and high (exclusive), and false otherwise.
fallsBetween low high item = your code goes here
Sample tests and output:

2. Using pattern matching, write a function allBetween, which should take three arguments, low, high, and a list ls, and should return only those items from ls that fall between low and high (exclusive). Use your fallsBetween from part 1, but do not use a built-in higher order function like map, foldl/r, or filter.
Sample tests and output:
> allBetween 5 8 [4, 5, 6, 7, 8, 9]
[6, 7]
3. Next, rewrite your function from part a to use an appropriate built-in higher order function instead (your function will now be much shorter). The output and parameters should remain the same.
4. Finally, rewrite your function to use a list comprehension. Once again, the output and parameters should remain the same.
5. This is the type signature for allBetween. Explain it to someone who doesnt know any Haskell.
allBetween :: Ord a => a -> a -> [a] -> [a]
> fallsBetween 5 8 6
True
> fallsBetween 5 8 7
True
> fallsBetween 5 8 5
False
Edit View Insert Format Tools Table

Edit View Insert Format Tools Table
12pt Paragraph
p
0 words

Question 6 1 pts
Reduce this Lambda Calculus expression using first eager, and then lazy evaluation:
(n.(n true) (n.s.((s false) n) (m.t.((t false) m) x.x)))

Edit View Insert Format Tools Table 12pt Paragraph
p
0 words

Quiz saved at 10:30am Submit Quiz