プログラミング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章で出てくるようですが、数学的な論証というのはこういう事を言うのでしょうか。

3. sumの掛ける版: product
myproduct [] = 1
myproduct (x : xs) = x * product xs

楽勝ですね*5

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]

ピボットと同じ数字がフェードアウトします。

*1:授業で使うから答えを書かないで欲しいですって?まぁ合っている保証は全くないので、いいんじゃないんでしょうか。

*2:プロフィールとか、漫画だとコメントとか既刊の本とかが書かれる所

*3:というか味わえました。

*4:チューニングとして、平均値に近い値をピボットとして選択するとかした方がよりよいとは思いますが。

*5:myが付いているのはproductが組み込みで用意されているからです