プログラミングHaskellを読む (1)
先日宣言したように、プログラミングHaskellを買ってきたので、ちまちまと読むことにします。
モチベーション維持のためにも、章ごとにメモや感想、練習問題の自分なりの解答を、このブログに書いていきたいと思います*1。
第1章 導入
まず、この章を読んでの第一感ですが、本のそで*2の部分に「プログラミングの経験はなくてもよく」とあるけれど、関数型言語に少しでも触れたことがないと、やっぱり全く経験なしでは無理な気がします。
理由としては色々ありますが、
- プログラミングの基本的な概念も知らずに読むのはやはり無理に感じる
- 「型」といわれても、その概念の意味に全く見当がつかないのでは、やはり読めないと思います
- 普通に命令型言語についても触れられている
ことがあげられるかと思います。
逆に関数型言語に少しでも経験があると、説明が体に染み渡る感覚を味わえます*3。
クイックソート
クイックソートがクールですね*4。whereがいかにも数学っぽい感じです。
qsort [] = [] qsort (x : xs) = qsort smaller ++ [x] ++ qsort larger where smaller = [a | a <- xs, a <= x] larger = [a | a <- xs, a > x]
一応Pythonでも似たように書けます。
# Python def qsort(lst): if len(lst) == 0: return [] x = lst[0] xs = lst[1:] smaller = [a for a in xs if a <= x] larger = [a for a in xs if a > x] return qsort(smaller) + [x] + qsort(larger)
練習問題
1. double (double 2)
の計算方法
double (double 2) = { 内側のdoubleを適用 } double (2 + 2) = { doubleを適用 } (2 + 2) + (2 + 2) = { 内側の+を適用 } 4 + 4 = { +を適用 } 8
途中の+の適用順次第でもっと多くの場合が存在しそうです。
2. xの値にかかわらずsum[x] = x
sumは
sum [] = 0 sum (x : xs) = x + sum(xs)
なので、
sum [x] = sum (x : []) = x + sum([]) = x + 0 = x
13章で出てくるようですが、数学的な論証というのはこういう事を言うのでしょうか。
4. 逆順のqsort
qsort [] = [] qsort (x : xs) = qsort larger ++ [x] ++ qsort smaller where smaller = [a | a <- xs, a <= x] larger = [a | a <- xs, a > x]
5. qsortで<=を<にすると…
qsort [2,2,3,1,1] = qsort [1,1] ++ 2 ++ qsort [3] = (qsort [] ++ 1 ++ qsort []) ++ 2 ++ (qsort [] ++ 3 ++ qsort[]) = 1 ++ 2 ++ 3 = [1,2,3]
ピボットと同じ数字がフェードアウトします。