algorithm DrRacket Scheme parallel

This question compares call-by-value (such as in Racket) and lazy evaluation (such as in Haskell). Although you will be asked summary questions (e.g., how much time does it take? why?) instead of detailed evaluation steps, it is still a good idea to take initiative and do some evaluation steps so you see the real trends. The following functions are given, in both Racket and Haskell. (The standard libraries already have similar functions under other names, but you need the explicit coding to reason about evaluation steps and costs.) Make list of integers from i to n-1: ``` (define (fromto i n) (if (< i n) (cons i (fromto (+ i 1) n)) '())) fromto i n = if i < n then i : fromto (i+1) n else [] ``` Get the kth element of a list. We only need the case 0 ≤ k < list length. ``` (define (index k xs) (match xs [(cons x xt) (if (equal? k 0) x (index (- k 1) xt))])) index k (x:xt) = if k==0 then x else index (k-1) xt ``` Part (a) [6 marks] -------- Let positive integer n≥3 be given. Comparing Racket with Haskell: How much time (up to big-Theta, e.g., Θ(1)? Θ(sqrt n)? Θ(n)?) does it take to evaluate `(index 2 (fromto 0 n))` in Racket? What is the computer doing to take that long? How much time does it take to evaluate `index 2 (fromto 0 n)` in Haskell? What is the computer doing differently, compared to the Racket version? Extra code for Parts (b) and (c) -------------------------------- Since Haskell lists are lazy, and we can also emulate lazy lists in Racket, the following are possible: Make infinite lazy list of integers from i onwards: ``` (define (from i) (list i (λ () (from (+ i 1))))) from i = i : from (i+1) ``` Get the kth element of an infinite lazy list. ``` (define (lzindex k xs) (match xs [(list x xt) (if (equal? k 0) x (lzindex (- k 1) (xt)))])) -- Haskell version of index already works for lazy lists. ``` Part (b) [9 marks] -------- Let positive integers k and n be given, and k<n. Comparing Haskell with Racket, and comparing `from` with `fromto` in Haskell: How much space (up to big-Theta) does it take to evaluate `index k (from 0)` in Haskell? What is the computer storing to take that much space? How much space does it take to evaluate `(lzindex k (from 0))` in Racket? What is the computer doing differently, compared to the Haskell version? How much space does it take to evaluate `index k (fromto 0 n)` in Haskell? What is the computer doing differently, compared to `index k (from 0)`? Part (c) [2 marks] -------- Write an improved implementation of the Haskell version of `from` by using `seq` suitably so that `index k (from 0)` stays in Θ(1) space. You may also add a local definition if it helps you use `seq`.