ZJU Lambda2017秋納筆試

先簡單介紹一下，ZJU Lambda是我這學期在浙大Google Camp社團辦的一個討論組，目的是聚集起浙大喜歡玩函數式的同學一起學習函數式相關知識。為了納新，我出了下面這套筆試題，難度我認為差不多就是《趣學指南》前8章的難度，尚未涉及Monad。考出來效果非常好，好幾個80+，90+，還有100的。出題人日常被吊打(1/1)。

本人才疏學淺，如果題目出現紕漏，還請各位知友多多指教。

第一部分

1. 以下屬於函數式編程理念的是（5分)

A. 過早的優化是萬惡之源

B. PHP是最好的語言

C. 代碼即數據，函數是一等公民

D. 變數的類型可以在運行時變化

2. 代數數據類型(algebraic data type)是函數式編程中非常重要的概念，請定義Int列表：

data IntList =______。（5分）

3. 若將代數數據類型(algebraic data type)與自然數建立映射，定義一個類型對應的自然數即為其可能的取值個數（以下稱作大小）。例如data Bool = True | False，Bool有兩個可能的取值True和False，那麼Bool的大小就為2；data T = E | S Bool Bool，T的取值有E;S True True;S True False;S False True;S False False一共5種，所以T的大小為5。以下說法錯誤的是（10分）

A. data C=ConsA A | ConsB B，則C的大小為A的大小和B的大小相加

B. data C=Cons A B，則C的大小為A的大小和B的大小相乘

C. data C=Cons (A->B)，則C的大小為A的大小和B的大小相乘

D. 存在加法單位元Void和乘法單位元()（在自然數運算中，0為加法單位元，1為乘法單位元）

4. 若兩個代數數據類型具有相同的「大小」，那麼這兩個代數數據類型之間一定存在一一對應關係，我們稱這樣的兩個類型同構(Isomorphism)。以下關於同構的說法錯誤的是（10分）

A. data Bool = True | False ，data Gender = Boy | Girl，Bool和Gender同構

B. data A = P | Q | R，data B = P | Q，A和B不同構，[A]和[B]也不同構([a]為a的列表)

C. 同構具有自反性（A與A同構），對稱性(若A與B同構，則B與A同構)與傳遞性(若A與B同構，B與C同構，則A與C同構)

D. ((A,B),C)與(A,B,C)同構

5. λ 演算是最小的通用程序設計語言。

(1) 用符號λ來定義函數。例如：λx.x+1定義了一個以x為變數的函數，它的返回值是x+1

λx. λy.x+y定義了一個以x為自變數的函數，返回值是一個函數，那個函數的功能是+x

(2) 兩項並置表示函數應用，例如 (λx.x+1) y表示把函數(λx.x+1)應用到y上

(3) λ演算的兩條規則：

alpha轉換：變換λ表達式中的變數名稱不改變函數本身。例: λx.x+1與λy.y+1等價

beta規約：函數應用時，用實際的參數替換λ符號後定義的參數。例：(λx.x+3/x) y經過beta規約後即為y+3/y

計算出下面的Lambda表達式的值，或指出其為無限循環（2+2+3+3=10分）

A. (λx.x+1) 5 =

B. (λf.λx.f (x+1)) (λy.2*y) 3 =

C. (λf.λx.f (f x)) (λy.y+2) 1 =

D. λf.(λx.f (x x)) (λx.f (x x)) g =

6. 在程序證明領域有一句話叫「類型即命題，程序即證明」，例如，某個函數的類型簽名為a->a，那麼它對應的命題為若a為真，則a為真。如果你能寫出一個類型簽名為a->a的函數，那麼你寫的程序就是這個命題的證明。下面關於程序證明的描述，錯誤的是（10分）

A. 你可以寫出一個a->a類型的通用函數，這表明，若a為真，則a為真

B. 你可以寫出一個Two a b->b類型的通用函數，這表明，若a且b為真，則b為真（Two的定義見2題）

C. 你不能寫出一個Either a b->a類型的通用函數，這表明，若a或b為真，則a不一定為真

D. 你不能寫出一個a->b->Two a b類型的通用函數，因為這個函數的類型簽名沒有對應的邏輯命題

第二部分 Haskell語言基礎（共50分）

1. 下面關於Haskell語言的說法，錯誤的是（5分）

A. 函數可以作為參數傳遞

B. []列表類型可以做到常數時間隨機訪問

C. 沒有for和while語句，實現循環應該用遞歸

D. 默認惰性求值

2. 以下常用函數的類型註解錯誤的是（5分）

A. foldl :: (Foldable t)=>(a->b->b)->b->t a->b

B. id :: a->a

C. head :: [a]->a

D. map ::

3. 表達式 map (+1) [1..10]的結果是____。 （5分）

4. 表達式 ((+1).(*2)) 3的結果是______。（5分）

5. 表達式foldl (xl _->[x:xs|x<-[1..n],xs<-xl,x `notElem` xs]) [[]] [1..n] where n=3的結果是___。（5分）

6. 請給出mapWithIndex :: (Int->a->b)->[a]->[b]的一個實現___________。(5分)

7. 寫出所有正偶數的列表t :: [Int] 的定義_____。（10分）

8. Maybe類型常用來表達一個可能存在的數據，它的定義如下

data Maybe a = Nothing | Just a

請完成函數除法函數maybeDiv :: Maybe Int -> Maybe Int -> Maybe

9. 請列出三個與Haskell相關的名詞（書、網站、工具鏈、Haskell的開源項目等）______________________________。（5分）

第三部分

1. 用結構歸納法證明（寫書面證明，不是寫代碼），二叉樹最多有2^(h-1)-1個節點，h為二叉樹高度，定義為從根到所有葉子的路徑長度的最大值。二叉樹的定義為 data Tree = Nil | Node Tree Tree

2. 你之前學過哪些編程語言，你認為用它們解決問題的思路是什麼？你認為用Haskell語言來解決問題與其他語言有哪些異同？

3. 寫一段你認為最能體現函數式編程思想的代碼，語言不限（函數式與非函數式的語言都可以）

參考答案

第一部分

1.C

2.Nil | Cons Int IntList

3.C

4.B

5.(1)6 (2)8 (3)5 (4)無限循環

6.D

第二部分

1.B

2.A

3.[2..11]

4.7

5.[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

6.mapWithIndex f xs = zipWith f [0..] xs （其它合理實現均可，下同）

7.[2,4...]

8.import Control.Applicative

maybeDiv::Maybe Int -> Maybe Int -> Maybe Int

maybeDiv x y

| y==Just 0 = Nothing

| otherwise = (liftA2 div) x y

9.隨便寫啦

第三部分是面試題，就沒有標準答案啦，歡迎各位在評論區暢談自己的見解。