Computer science Racket project
robeskywalker
Desktop.zip00-manifest.txt
The question-answer files (and the filenames to submit) are: eval.txt Treez.hs inference.txt TreezDef.hs is a support file for Treez.hs
eval.txt
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`.
inference.txt
This question is about type inference. The types of these literals are given: To infer the type of False: The answer is Bool. To infer the type of True: The answer is Bool. [10 marks] Following the type inference algorithm in this course, show the steps of inferring the polymorphic type for \c n -> c False (c True n)
Treez.hs
module Treez where import TreezDef -- This question develops tools for, among other applications, generating the -- infinite list of all finite binary trees, ordered from smaller trees to -- larger trees. -- -- We will represent a set as a list sorted in increasing order, and each -- element appears just once in the list. The set can be finite or infinite, so -- the list can be finite or infinite. -- First, You will implement some much-needed functions that work on this -- representation. -- Part (a) [4 marks] ----------- -- -- Union of two sets. Since the input lists are sorted, and you're producing a -- sorted list consisting of elements from both, this is basically the "merge" -- in mergesort, except: If an element is in both lists, -- -- * In merge, the output contains both occurrences. -- * In union, the output contains just one occurrence. -- -- Example: -- (non-neg multiples of 5) ∪ (non-neg multiples of 3) -- = union [0, 5..] [0, 3..] -- = [0, 3, 5, 6, 10, 12, 15, 18, ...] -- Note how 15 comes out just once. -- -- This function will be useful for the next part. union :: Ord a => [a] -> [a] -> [a] union = error "unimplemented" -- Part (b) [6 marks] ----------- -- -- "apply2 f xs ys" computes the list that represents this set: -- { f a b | a ∈ xs, b ∈ ys } -- We assume that f is strictly increasing, i.e., -- * if x1 < x2, then f x1 y < f x2 y -- * if y1 < y2, then f x y1 < f x y2 -- -- This is like the cartesian product of two sets but then you apply f to every -- pair. -- -- Example: All positive integers of the form 2^i * 3^j (natural i and j) in -- increasing order: -- -- {a*b | a is a power of 2, b is a power of 3} -- = apply2 (*) (iterate (\a -> a*2) 1) (iterate (\b -> b*3) 1) -- = [1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,...] -- -- How not to do it: Clearly, the simple list comprehension -- [ f a b | a <- xs, b <- ys ] -- Is wrong: Wrong order, and has extra problems in the infinite case. -- -- How to do it: The two base cases are obvious. For the recursive case: -- -- Suppose xs = x:xt, so x is the smallest element there, xt are the rest. -- Suppose ys = y:yt, so y is the smallest element there, yt are the rest. -- You are doing {f a b | a ∈ x:xt, b ∈ y:yt} -- Cool picture: Draw a table, on one axis are elements of xs, on the other axis -- are elements of ys, the cells are the "f a b"s. -- -- You can use a recursive call to cover {f a b | a ∈ xt, b ∈ yt} -- In fact, you can use the recursive call to cover a bit more, e.g., -- {f a b | a ∈ xt, b ∈ y:yt} -- In the picture, which region does the recursive call cover? -- So, how do you code up the rest? What is the rest? -- -- Another reminder: f x y is definitely the smallest element in the answer, -- since x is smallest in xs, y is smallest in ys, and f maps smaller elements -- to smaller elements. apply2 :: (Ord a, Ord b, Ord c) => (a -> b -> c) -> [a] -> [b] -> [c] apply2 = error "unimplemented" -- Now about the binary trees. -- -- TreezDef.hs has the binary tree type BinaryTree used in this question. -- -- It has the auto-generated sorting order ("deriving Ord"). However, we want -- to sort by tree size first, and then among trees of the same size, it's OK to -- use the auto-generated order. -- -- This is how the OBS type in TreezDef.hs can help. If we wrap our binary tree -- inside MkOBS, and if we make BinaryTree an instance of Sized (again in -- TreezDef.hs), then OBS comparison uses the size method first, then the -- auto-generated order, as wanted. -- Part (c) [2 marks] ----------- -- -- Implement the size method for BinaryTree. A straightforward recursion will -- do, doesn't have to be fancy. For this question, we simply count the total -- number of branch nodes (B). -- -- Example: size (B (B L L) L) = 2 -- because it contains 2 branch nodes. instance Sized BinaryTree where -- Part (d) [4 marks] ----------- -- -- Test of faith in recursive data equations and lazy lists. :) -- -- The set S of all finite binary trees satisfies this recursive equation (and -- is the smallest set that does): -- -- S = {L} ∪ {B lt rt | lt ∈ S, rt ∈ S} -- -- Since we use sorted lists for sets, and since Leaf is clearly the smallest -- element and should be first, it looks like -- -- S = L : {B lt rt | lt ∈ S, rt ∈ S} -- -- and we know that apply2 can help with the {B lt rt | lt ∈ S, rt ∈ S} part. -- -- But wait! You need the OBS/MkOBS wrapper so apply2 uses the correct order! -- How to adjust for that? -- -- Implement obstreez below for the infinite list of binary trees, each tree -- wrapped inside MkOBS, so that smaller trees are ordered first by apply2. -- -- Then treez below just needs to unwrap by unOBS to give you the list of the -- trees themselves. obstreez :: [OBS BinaryTree] obstreez = error "unimplemented" treez :: [BinaryTree] treez = map unOBS obstreez -- Example: take 9 treez = -- [L, -- size 0 -- B L L, -- size 1 -- B L (B L L), B (B L L) L, -- size 2 -- B L (B L (B L L)), B L (B (B L L) L), B (B L L) (B L L), -- size 3 -- B (B L (B L L)) L, B (B (B L L) L) L -- size 3 cont. -- ]
TreezDef.hs
module TreezDef where data BinaryTree = L | B BinaryTree BinaryTree deriving (Eq, Ord, Show) -- L = leaf, B = branch. The data constructor names are kept short for shorter -- printing outputs. -- "OBS" stands for "ordered by size". This is a wrapper type to select the Ord -- instance below. See below for what good this does. data OBS t = MkOBS t deriving (Eq, Show) -- Unwrapper. unOBS :: OBS t -> t unOBS (MkOBS a) = a -- This class is really just for the Ord (OBS t) instance below. class Sized t where size :: t -> Int -- we expect non-neg int -- If t is an Ord instance and also a Sized instance, then the Ord instance for -- the OBS wrapper compares by first comparing sizes, and only when tie, by t's -- own <=. instance (Ord t, Sized t) => Ord (OBS t) where MkOBS a1 <= MkOBS a2 = s1 < s2 || s1 == s2 && a1 <= a2 where s1 = size a1 s2 = size a2 -- Example: Strings are normally sorted alphabetically: -- "abbbbbb" < "ack" < "ask" -- If I want: Sort by length, and if two strings have the same length, then -- alphabetical order is OK: instance Sized [a] where size xs = length xs -- Then: MkOBS "ack" < MkOBS "ask" < MkOBS "abbbbbb".
