プログラミングHaskellを読み始めた

会社の勉強会でプログラミングHaskellを読むことになった。（来週から始めるので楽しみ）とりあえず１章を読んで練習問題まで解いたのでメモをまとめておく。

第1章導入

Haskellにおける関数 ... 1つ以上の引数を取って1つの結果を返す変換器

関数プログラミング ... 一般的に、「計算の基本は関数を引数に適用すること」というプログラミング手法のこと

関数型言語 ... 関数プログラミングの手法を「提供」し「奨励」しているプログラミング言語。

Haskellの明瞭簡潔さを示す例としてのクイックソート（任意の数値型のリストに対して要素を昇順に並べ替えたリストを生成する）

-- xはqsortの引数として与えられるリストの最初の要素、xsは残りのリスト
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
               where
                 smaller = [a | a <- xs, a <= x]
                 larger  = [b | b <- xs, b > x]

---------------------------------------------------
-- `++` は2つのリストを連結する二項演算子
  qsort [3, 5, 1, 4, 2]
= qsort [1, 2] ++ [3] ++ qsort [5, 4]
= (qsort [] ++ [1] ++ qsort [2] ) ++ [3] ++ (qsort [4] ++ [5] ++ qsort [])
= ([] ++ [1] ++ [2]) ++ [3] ++ ([4] ++ [5] ++ [])
= [1, 2] ++ [3] ++ [4, 5]
= [1, 2, 3, 4, 5]

クイックソートの型

-- 任意の順序（Ord）型aに対し、qsortはその型を要素として持つリストを同種のリストに変換する
-- 順序型とは、数値や文字列などの順序を持つ型全般のこと
qsort :: Ord a => [a] -> [a]

モナドの説明もちょっと出てきたけど難しかった。後の章読みながら理解しよう

1.7 練習問題

double (double 2)の結果を算出する別の計算方法を考える

  double (double 2)
= double (2 + 2)
= (2 + 2) + (2 + 2)
= 4 + (2 + 2)
= 4 + 4
= 8

xの値によらず sum [x] = x であることを示す

-- 関数sumの定義
sum []     = 0
sum (n:ns) = n + sum ns

-- 問２の解
  sum [x]
= x + sum []
= x + 0
= x

数値のリストに対し積を計算する関数productを定義し、product [2, 3, 4] = 24 となることを示す

-- 関数productの定義
product [] = 1
product (n:ns) = n * product ns

-- 一応型も定義（sum関数を真似してみた）
product :: Num a => [a] -> a

  product [2, 3, 4]
= 2 * product [3, 4]
= 2 * (3 * product [4])
= 2 * (3 * (4 * product []))
= 2 * (3 * (4 * 1))
= 24

リストを降順に整列するに関数qsortの定義を変えるにはどうすれば良いか

-- リストを降順に整列するqsort
qsort [] = []
qsort(x:xs) = qsort larger ++ [x] ++ qsort smaller 
              where
                smaller = [a | a <- xs, a <= x]
                larger  = [b | b <- xs, b > x]

-- 具体的な値で降順ソートしてみる
  qsort [3, 5, 1, 4, 2]
= qsort [5, 4] ++ [3] ++ qsort [1, 2]
= (qsort [] ++ [5] ++ qsort [4]) ++ [3] ++ (qsort [2] ++ [1] ++ qsort [])
= [5, 4] ++ [3] ++ [2, 1]
= [5, 4, 3, 2, 1]

qsortの定義で、≤を<に置き換えるとどのような影響があるか

-- 本書で与えられているqsortの定義（数値リストを昇順に並べ変える）
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
               where
                 smaller = [a | a <- xs, a <= x]
                 larger  = [b | b <- xs, b > x]

-- <=を<に置き換えたqsortの定義
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
               where
                 smaller = [a | a <- xs, a < x]
                 larger  = [b | b <- xs, b > x]

-- <=を<に置き換えたqsortで[2, 2, 3, 1, 1]をソートしてみる
  qsort [2, 2, 3, 1, 1]
= qsort [1, 1] ++ [2] ++ qsort [3] -- 残ったリストの中の要素2が、larger, smallerのどちらにも該当しないため消えてしまう
= (qsort [] ++ [1] ++ qsort []) ++ [2] ++ qsort [3] -- 同上の理由で1が消える
= [1] ++ [2] ++ [3]
= [1, 2, 3]

-- 解
-- qsortの定義で<=を<に置き換えると、与えられたリストの要素として同一の数値が複数存在する場合、
-- 重複した値が解のリストから消えてしまうという影響がある。

Haskellは純粋関数型言語なので関数が副作用を持つことは無いと思っていたが、どうもそうではない？ぽい。型によって純粋な関数と副作用を引き起こす関数を明確に区別することができ、それこそHaskellの中心となる機能であるとのこと。まだ全然理解できていないけれど、この本を読み終わる頃には理解できているといいな。

第1章 導入

第1章導入