课程名称︰程式语言 课程性质︰选修 课程教师︰穆信成 开课学院：管理学院 开课系所︰资讯管理学系 考试日期（年月日）︰11/7 (四) 考试时限（分钟）：9:10-12:10 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : (考试允许携入任何讲义/笔记/参考资料. 原试卷中斜体/程式字以高亮标示) Programming Languages: Midterm Examination Shin-Cheng Mu Nov. 7, 2013 You may assume that knowledge about arithmetic (e.g. ( ×) is associative, multiplication distributes over addition, etc) need no further proof and may be taken as axioms. Algebraic proofs or derivations need not be carried out in glory details -- you may skip some steps that you think are trivial. Do label the important steps, however, especially the step(s) where you use induction. You can use all Haskell functions in the standard prelude, mentioned in the lectures. 1. (10 points) A suffix of a list xs is a consecutive segment of xs that ends at the right end of xs. Define a function lmamrm :: [Int] → Int such that lmamrm xs returns the num- ber of suffixes of xs whose leftmost element is less than or equal to its rightmost element. (The funny name lmamrm stands for ``leftmost-at-most-rightmost".) For example, [4, 3, 9, 3] has two such suffixes: [3, 9, 3] and [3], thus lmamrm [4, 3, 9, 3] = 2. Hints: 1. A one-line definition will do. 2. we have already mentioned a function, in the standard library, that returns all suffixes of a list. 3. A list must be non-empty to have a leftmost and a rightmost element - which could be the same element. There was a function in the standard library check- ing whether a list is empty. If you cannot find it, define your own. 2. (15 points) Prove the property: sum。map (y ×) = (y ×)。sum 3. (15 points) Recall the definition of (!!) such that xs !! n yields the nth element in xs (counting from 0): (!!) :: [a] → Nat → a (x : xs) !! 0 = x (x : xs) !! (1+ n) = xs !! n. Consider the definition below geo :: Int → [Int] geo y = 1 : map (y ×) (geo y). n Prove that geo y !! n = y for all n :: Nat. 4. (15 points) An interleaving of two lists xs and ys is a permutation of the elements of both lists such that the mem- bers of xs appear in their original order, and so does the member of ys. Define interleave :: [a] → [a] → [[a]] such that interleave xs ys is the list of interleaving of xs and ys. For example, interleave [1, 2, 3] [4, 5] yields: [[1,2,3,4,5], [1,2,4,3,5], [1,2,4,5,3], [1,4,2,3,5], [1,4,2,5,3], [1,4,5,2,3], [4,1,2,3,5], [4,1,2,5,3], [4,1,5,2,3], [4,5,1,2,3]]. Hint: I would use an inductive definition. 5. A list ys is a sublist of xs if we can obtain ys by remov- ing zero or more elements from xs. For example, [2, 4] is a sublist of [1, 2, 3, 4], while [3, 2] is not. The list of all sublists of [1, 2, 3] is: [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]. (a) (20 points) Define a function sublist :: [a] → [[a]] that computes the list of all sublists of the given list. Hint: to form a sublist of xs, each element of xs could either be kept of dropped. (b) (10 points) Define a function maximumBy :: (a → Int) → [a] → a such that maximumBy f takes a (non-empty) list xs as its input, and returns an element x such that x is an element of xs and, for all element y in xs, f x ≧ f y. Hint: there are many ways to define maximumBy. I would perhaps go for an inductive definition. (c) (5 points) Let Item be some datatype, representing cer- tain items, for which two functions are defined: value :: Item → Int, weight :: Item → Int. Define two functions valList :: [Item] → Int and weightList :: [Item] → Int that respectively compute the total value and weight, give a list of items. (d) (10 points) Recall the 0-1 knapsack problem: given a list of items, we want to pick a sublist of the items that is as valuable as possible, whose total weight is no more than a weight limit. Give a one-line program knapsack :: Int → [Item] → [Item] knapsack w ... where w is the weight limit, that specifies (or, computes) the 0-1 knapsack problem, using the functions defined above, together with some library functions. It is only a specification, thus it does not matter if it is very slow. (We will learn how to optimise it in later courses.) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 118.166.61.86 ※ 编辑: suhorng 来自: 118.166.61.86 (11/09 00:26) ※ 编辑: suhorng 来自: 118.166.61.86 (11/09 00:26)