LYAHFGG!まとめ(Part1)

前置き

すばらしい(英文の)記事に出会うと、これを翻訳して他の人にも読ませたいと思うのが人情というものですが、その思いは数段落で挫折するのが常です。Miran Lipovača氏によるHaskellのチュートリアルLearn You a Haskell for Great Good!も、そんな記事の一つ。

翻訳する日本語力も、ダイジェスト版を執筆するほどの経験も無いので、せめて自分用に要点の箇条書きを残しておこうと思います。Part1は、I/Oの手前まで。後半はPart2で。

  • 少しだけ、順番を入れ替えたりサンプルコードを追加した所があります
  • また、☆の部分は私の独り言です
  • 基本的には、コードを示した後でポイントを箇条書きにする、というスタイルになっています
  • 用語、ghciの使い方、及び関数リファレンスは別ページ「LYAHFGG!まとめ(リファレンス)」に整理します

1.Introduction

About this tutorial

  • 命令型言語(C, C++, Java, Python, ...)経験者が対象
  • 自分は2回挫折した

So what's Haskell?

  • 純粋な関数型言語
  • 副作用なし
  • 参照透明性(同じ関数を同じ引数で呼べば、いつでも同じ結果が返る)
  • 遅延評価
  • 静的型付け
  • 型推論
  • 1987年に生まれ、最新仕様は2003年のHaskell Report

What you need to dive in

GHCi, version 7.0.4: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> :set prompt "ghci> "
ghci>

2.Starting Out

Ready, set, go!

ghci> 5 / 2
2.5
ghci> (50 * 100) - 4999
1
ghci> True && False
False
ghci> False || True
True
ghci> not False
True
ghci> 5 == 5
True
ghci> 5 /= 5
False
ghci> "hello" == "hello"
True
ghci> :t (==)
(==) :: (Eq a) => a -> a -> Bool
  • 除算 / は実数扱い
  • 括弧で優先順位を明示
  • 不等号は /=
  • 上記の演算子は中置の関数
  • 関数名が記号のみなら、デフォルトで中置とみなされる
  • そのような関数を中置の関数適用以外で使う場合は()で囲む
ghci> succ 8
9
ghci> min 9 10
9
ghci> min 3.4 3.2
3.2
ghci> max 100 101
101
ghci> succ 9 + max 5 4 + 1
16
ghci> 92 `div` 10
9.2
  • 関数名 + スペース + 引数で、関数適用
  • 関数適用は最も優先度が高い
  • 前置の関数を中置で使う場合は、バッククオートで囲む

Baby's first functions

baby.hs

doubleMe x = x + x
  • ソースファイルの拡張子は*.hs
ghci> :l baby
[1 of 1] Compiling Main             ( baby.hs, interpreted )
Ok, modules loaded: Main.
ghci> doubleMe 9
18
ghci> doubleMe 8.3
16.6
  • ソースをロードするときは、拡張子不要
doubleMe x = x + x

doubleUs x y = doubleMe x + doubleMe y

doubleSmallNumber x = if x > 100
  then x
  else x*2

doubleSmallNumber' x = (if x > 100 then x else x*2) + 1

conanO'Brien = "It's a-me, Conan O'Brien!"
  • 定義順序は不問
  • ifも式なので、elseは必須
  • ifは1行で書いてもOK
  • 関数名に ' を使用可
  • 関数名は大文字で始めてはならない
  • 関数が引数を取らない場合、定義(または名前)と呼ぶ

An intro to lists

ghci> let lostNumbers = [4,8,15,16,23,42]
ghci> lostNumbers
[4,8,15,16,23,42]
ghci> [1,2,3,4] ++ [9,10,11,12]
[1,2,3,4,9,10,11,12]
ghci> "hello" ++ " " ++ "world"
"hello world"
ghci> ['w','o'] ++ ['o','t']
"woot"
ghci> 'A':" SMALL CAT"
"A SMALL CAT"
ghci> 5:[1,2,3,4,5]
[5,1,2,3,4,5]
ghci> "Steve Buscemi" !! 6
'B'
ghci> [9.4,33.2,96.2,11.2,23.25] !! 1
33.2
ghci> [3,2,1] > [2,1,0]
True
  • ghciのトップレベルのletは、名前の定義(スコープはグローバル)
  • リストの要素の型は同じ
  • 文字列は文字のリスト
  • ++で連結(リストの末尾を探すので遅いかも)
  • :でcons(末尾を探す必要がないので早い)
  • [1,2,3]は1:2:3:[]のシンタックスシュガー
  • !!でリスト要素にインデックスアクセス(0オリジン)
  • 要素同士が比較可能なら、リスト同士も比較可能

Texas ranges

ghci> [1..20]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
ghci> ['a'..'z']
"abcdefghijklmnopqrstuvwxyz"
ghci> ['K'..'Z']
"KLMNOPQRSTUVWXYZ"
ghci> [2,4..20]
[2,4,6,8,10,12,14,16,18,20]
ghci> [3,6..20]
[3,6,9,12,15,18]
ghci> take 6 [3,6..]
[3,6,9,12,15,18]
  • 1ずつ増える場合、途中を..で略す
  • 差分が1以外の場合は、最初の2つを示す
  • 上限値を指定しなければ無限リスト

I'm a list comprehension

ghci> [x*2 | x <- [1..10]]
[2,4,6,8,10,12,14,16,18,20]
ghci> [x*2 | x <- [1..10], x*2 >= 12]
[12,14,16,18,20]
ghci> [ x | x <- [10..20], x /= 13, x /= 15, x /= 19]
[10,11,12,14,16,17,18,20]
ghci> [ x*y | x <- [2,5,10], y <- [8,10,11]]
[16,20,22,40,50,55,80,100,110]
ghci> let length' xs = sum [1 | _ <- xs]
ghci> let xxs = [[1,3,5,2,3,1,2,4,5],[1,2,3,4,5,6,7,8,9],[1,2,4,2,1,6,3,1,3,2,3,6]]
ghci> [ [ x | x <- xs, even x ] | xs <- xxs]
[[2,2,4],[2,4,6,8],[2,4,2,6,2,6]]
  • 集合の内包表記っぽく書く
  • パイプの前が出力関数
  • パイプの後で、入力集合を変数にバインドし、フィルタリング条件となる述語を指定する
  • 複数の述語を書けば、論理積となる
  • 複数の入力集合を書くと、直積に対して繰り返す
  • _にバインドすると、繰り返すのみで値は捨てる
  • ネストしてもOK
  • ☆リストの名前には、xsのようにsを付けるのが慣例みたい(数字のリストならns、文字のリストならcs、文字列のリストならcssとか)

Tuples

("Christopher", "Walken", 55)
()
  • 要素数は固定
  • ☆要素が1つのタプルはあり得ないが、空のタプルはOK
  • 要素は同じ型でなくて良い
  • 要素同士が比較可能なら、タプル同士も比較可能

3.Types and Typeclasses

Believe the type

ghci> :t 'a'
'a' :: Char
ghci> :t True
True :: Bool
ghci> :t "HELLO!"
"HELLO!" :: [Char]
ghci> :t (True, 'a')
(True, 'a') :: (Bool, Char)
ghci> :t 4 == 5
4 == 5 :: Bool
ghci> :t ()
() :: ()
ghci> :t GT
GT :: Ordering
  • ::の後ろが型名
  • 型名は大文字で始める
  • Intは上限と下限がある整数
  • Integerは制限無し
  • Floatは単精度浮動小数点数
  • Doubleは倍精度浮動小数点数
  • Boolの値はTrueとFalseのみ
  • Charは文字で、リテラルはシングルクオートで囲む
  • ()のことをユニットと呼ぶ
  • ()は型名でもあり、その唯一の値が()
  • Orderingの値は、GT、LT、EQ
removeNonUppercase :: [Char] -> [Char]
removeNonUppercase st = [ c | c <- st, c `elem` ['A'..'Z']]

addThree :: Int -> Int -> Int -> Int
addThree x y z = x + y + z
  • 関数にも型がある
  • 関数定義の前に関数の型を宣言する(オプション)

Type variables

ghci> :t head
head :: [a] -> a
ghci> :t fst
fst :: (a, b) -> a
  • aは型変数で、任意の型を意味する(プレースホルダみたいなもの)
  • 通常は、a, b, cのような短い名前を使う
  • 関数が型変数を持つことで多態性を実現

Typeclasses 101

ghci> :t (==)
(==) :: (Eq a) => a -> a -> Bool
ghci> :t fromIntegral
fromIntegral :: (Num b, Integral a) => a -> b
  • Eqは型クラス
  • 型は、型クラスのインスタンス
  • 関数の型に含まれる => は、型クラス制約
  • (Eq a)は、型aを、型クラスEqのメンバー(インスタンス)に制限する
  • 複数の型クラス制約がある場合は、カンマ区切りで列挙する

例えば、以下のような型クラスがある。

  • Eqは、==と/=を適用できる
  • Ordは、>、<、>=、<=、compare
  • Showは、show関数で文字列へ変換可能
  • Readは、read関数で文字列から変換可能
  • Enumは、succ関数やpred関数を適用できる
  • Boundedは、minBound関数とmaxBound関数を適用可能
  • Numは、実数
  • Integralは、IntとInteger
  • Floatingは、FloatとDouble

4.Syntax in Functions

Pattern matching

factorial :: (Integral a) => a -> a
factorial 0 = 1
factorial n = n * factorial (n - 1)

addVectors :: (Num a) => (a, a) -> (a, a) -> (a, a)
addVectors (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)

tell :: (Show a) => [a] -> String
tell [] = "The list is empty"
tell (x:[]) = "The list has one element: " ++ show x
tell (x:y:[]) = "The list has two elements: " ++ show x ++ " and " ++ show y
tell (x:y:_) = "This list is long. The first two elements are: " ++ show x ++ " and " ++ show y
  • 引数がリストやタプルの場合、1つの引数を複数の変数へバインドできる
  • その場合は、()で囲む(☆というより、評価の優先順位を制御するためか?)
  • (x:y:[])は、[x,y]と書いてもOK
capital :: String -> String
capital "" = "Empty string, whoops!"
capital all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x]
  • 部分(つまりxとxs)にマッチさせつつ、@で全体も捕捉する

Guards, guards!

bmiTell :: (RealFloat a) => a -> String
bmiTell bmi
    | bmi <= 18.5 = "You're underweight, you emo, you!"
    | bmi <= 25.0 = "You're supposedly normal. Pffft, I bet you're ugly!"
    | bmi <= 30.0 = "You're fat! Lose some weight, fatty!"
    | otherwise   = "You're a whale, congratulations!"
  • |と=の間にあるのがガード
ghci> show otherwise
"True"
  • otherwiseは常にTrue
  • (otherwiseが無くて)どのガードにも適合しなければ、次のパターンへ行く

Where!?

bmiTell :: (RealFloat a) => a -> a -> String
bmiTell weight height
    | bmi <= skinny = "You're underweight, you emo, you!"
    | bmi <= normal = "You're supposedly normal. Pffft, I bet you're ugly!"
    | bmi <= fat    = "You're fat! Lose some weight, fatty!"
    | otherwise     = "You're a whale, congratulations!"
    where bmi = weight / height ^ 2
          skinny = 18.5
          normal = 25.0
          fat = 30.0

bmiTell' :: (RealFloat a) => a -> a -> String
bmiTell' weight height
    | bmi <= skinny = "You're underweight, you emo, you!"
    | bmi <= normal = "You're supposedly normal. Pffft, I bet you're ugly!"
    | bmi <= fat    = "You're fat! Lose some weight, fatty!"
    | otherwise     = "You're a whale, congratulations!"
    where bmi = weight / height ^ 2
          (skinny, normal, fat) = (18.5, 25.0, 30.0)

initials :: String -> String -> String
initials firstname lastname = [f] ++ ". " ++ [l] ++ "."
    where (f:_) = firstname
          (l:_) = lastname
  • whereの後に定義した名前は、その関数内の、そのパターン内でのみ有効
  • 複数の名前を定義するときは改行で区切り、先頭の名前とインデントを揃える
  • whereで名前を定義するのにパターンマッチを使ってもいい
calcBmis :: (RealFloat a) => [(a, a)] -> [a]
calcBmis xs = [bmi w h | (w, h) <- xs]
    where bmi weight height = weight / height ^ 2
  • whereで関数を定義してもOK

Let it be

cylinder :: (RealFloat a) => a -> a -> a
cylinder r h =
    let sideArea = 2 * pi * r * h
        topArea = pi * r ^2
    in  sideArea + 2 * topArea
  • let BINDINGS in EXPRESSION
  • BINDINGSはEXPRESSION内でのみ有効
  • 複数のバインドは改行で区切り、先頭の名前とインデントを揃える
ghci> 4 * (let a = 9 in a + 1) + 2
42
ghci> [let square x = x * x in (square 5, square 3, square 2)]
[(25,9,4)]
ghci> (let a = 100; b = 200; c = 300 in a*b*c, let foo="Hey "; bar = "there!" in foo ++ bar)
(6000000,"Hey there!")
ghci> (let (a,b,c) = (1,2,3) in a+b+c) * 100
600
  • let自体が式である
  • 複数のバインドを1行で書く場合はセミコロンで区切る
  • letでパターンマッチを使ってもいい
calcBmis :: (RealFloat a) => [(a, a)] -> [a]
calcBmis xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2, bmi >= 25.0]

calcBmis' :: (RealFloat a) => [(a, a)] -> [a]
calcBmis' xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2, let minbmi = 25.0 in bmi >= minbmi]
  • リスト内包の内部で使ってもいい
  • その場合、inは無し
  • バインドされた名前は、出力関数と、letの後ろでのみ有効
  • リスト内包の述語の中でletを使う場合はinを付ける(スコープは述語内)

Case expressions

head' :: [a] -> a
head' xs = case xs of [] -> error "No head for empty lists!"
                      (x:_) -> x
  • パターンマッチはcase式のシンタックスシュガー
  • 先頭のパターンとインデントを揃えること
describeList :: [a] -> String
describeList xs = "The list is " ++ case xs of [] -> "empty."
                                               [x] -> "a singleton list."
                                               xs -> "a longer list."

describeList :: [a] -> String
describeList xs = "The list is " ++ what xs
    where what [] = "empty."
          what [x] = "a singleton list."
          what xs = "a longer list."
  • caseでも書けるし、whereとパターンマッチでも書ける

5.Recursion

Hello recursion!

  • edge conditionが決め手

Maximum awesome

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs)
    | x > maxTail = x
    | otherwise = maxTail
    where maxTail = maximum' xs

A few more recursive functions

replicate' :: (Num i, Ord i) => i -> a -> [a]
replicate' n x
    | n <= 0    = []
    | otherwise = x:replicate' (n-1) x

take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
    | n <= 0   = []
take' _ []     = []
take' n (x:xs) = x : take' (n-1) xs

reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]

repeat' :: a -> [a]
repeat' x = x:repeat' x

zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys

elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
    | a == x    = True
    | otherwise = a `elem'` xs
  • 無限リストもOK
  • ただし他の関数と組み合わせて使う

Quick, sort!

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in  smallerSorted ++ [x] ++ biggerSorted

Thinking recursively

6.Higher Order Functions

Curried functions

ghci> max 4 5
5
ghci> (max 4) 5
5
  • (max 4)は部分適用で、引数を1つ取り4と比較する関数を返す
max :: (Ord a) => a -> a -> a
max :: (Ord a) => a -> (a -> a)
  • すべての関数は実は引数を1つだけ取る
  • (見かけ上)複数の引数を取る関数適用は、実は部分適用の繰り返し
multThree :: (Num a) => a -> a -> a -> a
multThree x y z = x * y * z
ghci> multThree 3 5 9
135
  • 実は、((multThree 3) 5) 9
compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred = compare 100
  • (見かけ上)2つの引数を取るcompareへの部分適用を利用した関数定義
  • 関数定義部分に引数が記述されてない → pointless style(pointはトポロジーの点に由来)
divideByTen :: (Floating a) => a -> a
divideByTen = (/10)

subtractFour :: (Num a) => a -> a
subtractFour = subtract 4
  • ()で囲むとセクション
  • セクションを使って、第2引数を先に部分適用する
  • ただし減算関数 - だけはセクションで書けない
  • なぜなら、(-4)がマイナス4と扱われるため
  • x - 4 みたいな関数が欲しければsubtractを使う
  • (`subtract` 4)じゃないよ
  • subtract a b で、b - a

Some higher-orderism is in order

applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

flip' :: (a -> b -> c) -> b -> a -> c
flip' f y x = f x y

Maps and filters

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerSorted = quicksort (filter (<=x) xs)
        biggerSorted = quicksort (filter (>x) xs)
    in  smallerSorted ++ [x] ++ biggerSorted

largestDivisible :: (Integral a) => a
largestDivisible = head (filter p [100000,99999..])
    where p x = x `mod` 3829 == 0
  • Haskellはlazyなので、あるリストにmapやfilterを何回かけてもリスト走査は1回(☆ホント?)
  • ☆あえて正格評価するための、($!)という関数もある
ghci> let listOfFuns = map (*) [0..]
ghci> (listOfFuns !! 4) 5
20
  • listOfFunsは、0*x, 1*x, 2*x, ... なリスト
  • 4番目の要素(つまり4*x)を取り出し、引数5へ適用

Lambdas

numLongChains :: Int
numLongChains = length (filter (\xs -> length xs > 15) (map chain [1..100]))
ghci> zipWith (\a b -> (a * 30 + 3) / b) [5,4,3,2,1] [1,2,3,4,5]
[153.0,61.5,31.0,15.75,6.6]
  • \で始め、=の代わりに->を使う
  • それ以外は関数定義と同じ
ghci> map (+3) [1,6,3,2]
[4,9,6,5]
ghci> map (\x -> x + 3) [1,6,3,2]
[4,9,6,5]
  • 部分適用で書けるならラムダを使うまでもない
ghci> map (\(a,b) -> a + b) [(1,2),(3,5),(6,3),(2,6),(2,5)]
[3,8,9,8,7]
  • パターンマッチも可能だが、複数のパターンは持てない
addThree :: (Num a) => a -> a -> a -> a
addThree = \x -> \y -> \z -> x + y + z
  • ()で囲まなければ、行末までがラムダ

Only folds and horses

sum' :: (Num a) => [a] -> a
sum' = foldl (+) 0

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x acc -> f x : acc) [] xs

reverse' :: [a] -> [a]
reverse' = foldl (flip (:)) []
  • foldl系の関数は無限リストには使えない

☆補足: なぜ無限リストに対してfoldlを使えないのか

まず、foldlとfoldrの実装を見てみましょう。

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = go z0 xs0
  where
    go z [] = z
    go z (x:xs) = go (f z x) xs

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z xs = go xs
  where
    go [] = z
    go (y:ys) = y `f` go ys

foldrは無限リストにも適用できるが、foldlはダメ。原文では、これについて明確な解説を省いています。他のサイトも調べてみましたが、納得のいく説明は見つかりませんでした。

無限リストに対する、foldlとfoldrの展開形を比較してみると…

  • foldl f i [a1,a2,a3,…] ⇒ f(…f(f(f(i,a1),a2),a3),…,a∞)
  • foldr f i [a1,a2,a3,…] ⇒ f(a1,f(a2,f(a3,…,f(a∞,i)…)))

となり、foldlの場合はa1やa2が関数コールのネストの深い方(中心側)に来るのに対し、foldrの場合は外側に来る、というのが本質的には関係してそうな気がします。でも、筋の通った説明はできません。

そもそもfoldrだって、どんな無限リストにも使えるというわけではないですね。

ghci> foldr (+) 0 [1..]             --これは終わらない。

では、どんな場合なら使えるのか? 答えは「有限個の要素だけで結果が評価できる場合は使える」です。例えば(&&)や(:)と組み合わせる場合ですね。

自然数に(<3)をmapして[Bool]な無限リストを作り、foldrとfoldlを適用してみましょう。

ghci> let ttf = map (<3) [1..]
ghci> take 10 $ ttf
[True,True,False,False,False,False,False,False,False,False]
ghci> foldr (&&) True $ ttf
False
ghci> foldl (&&) True $ ttf    --これは終わらない。

上記のfoldrが成立するカラクリを理解するには、&&の実装を見る必要があります。

(&&) :: Bool -> Bool -> Bool
True && x = x
False && _ = False

「左オペランドがFalseなら右オペランドは不問」というのがミソです。これと、foldr (&&) Trueの展開形が

a1 && (a2 && (a3 && …(a∞ && True)…))

となることを合わせると、a1からa3だけで評価が終わります(a3がFalseだから)。一方、foldlの方は、a1やa2が右オペランド側に来るので、foldrのようにはいきません。

a∞ && (…(((True && a1) && a2) && a3) …)

ちなみに、初期値がFalseならfoldlでも1発目で結果が出るのか? というと、出ません。

ghci> foldl (&&) False $ ttf    --これも終わらない。

ここで実験。&&とソックリの関数aaを定義してみましょう。

aa :: Bool -> Bool -> Bool
x `aa` True = x
_ `aa` False = False

右オペランドがFalseなら終わります。これでfoldrとfoldlの立場が逆転か???

ghci> foldr aa True $ ttf    --これは終わらない。
ghci> foldl aa True $ ttf    --これも終わらない。

共倒れでした。foldrは予想通りとして、foldlには本質的にlazyな機構が作用しないようです。

あと、気付いたんですが、無限リストに対してfoldrを使える場合、初期値は何でも良いです。逆に、初期値が結果に響くような対無限リストfoldrは終わらないはずです。

Function application with $

ghci> sum $ filter (> 10) $ map (*2) [2..10]
80
ghci> map ($ 3) [(4+), (10*), (^2), sqrt]
[7.0,30.0,9.0,1.7320508075688772]
  • $は最も優先度が低い
  • スペースによる関数適用は左結合だが、$は右結合

Function composition

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
ghci> map (negate . abs) [5,-3,-6,7,-3,2,-19,24]
[-5,-3,-6,-7,-3,-2,-19,-24]
ghci> map (negate . sum . tail) [[1..5],[3..6],[1..7]]
[-14,-15,-27]
  • 関数合成は右結合
fn x = ceiling (negate (tan (cos (max 50 x))))

fn = ceiling . negate . tan . cos . max 50
  • fnをpointless styleで書くには、関数合成を使う必要がある

7.Modules

Loading modules

  • 標準ライブラリは複数のmoduleに分かれている
  • Preludeがデフォルトでインポートされる
import Data.List

numUniques :: (Eq a) => [a] -> Int
numUniques = length . nub              --nubが使える。
import Data.List (nub, sort)           --nubとsortだけ使いたい。
import Data.List hiding (nub)          --nub以外を使いたい。
import qualified Data.Map

Data.Map.null Data.Map.empty           --モジュール名で名前空間を指定。
import qualified Data.Map as M

M.null M.empty                         --名前空間の別名。

Data.List

Data.Char

Data.Map

  • ハッシュテーブルという意味でのマップ
  • PreludeやData.Listと名前が衝突するのでqualified importで

Data.Set

  • 集合
  • PreludeやData.Listと名前が衝突するのでqualified importで

Making our own modules

module Geometry
( sphereVolume
, sphereArea
, cubeVolume
, cubeArea
, cuboidArea
, cuboidVolume
) where

sphereVolume :: Float -> Float
sphereVolume radius = (4.0 / 3.0) * pi * (radius ^ 3)

sphereArea :: Float -> Float
sphereArea radius = 4 * pi * (radius ^ 2)

cubeVolume :: Float -> Float
cubeVolume side = cuboidVolume side side side

cubeArea :: Float -> Float
cubeArea side = cuboidArea side side side

cuboidVolume :: Float -> Float -> Float -> Float
cuboidVolume a b c = rectangleArea a b * c

cuboidArea :: Float -> Float -> Float -> Float
cuboidArea a b c = rectangleArea a b * 2 + rectangleArea a c * 2 + rectangleArea c b * 2

rectangleArea :: Float -> Float -> Float
rectangleArea a b = a * b
  • rectangleAreaはexportしない
module Geometry.Sphere
( volume
, area
) where

volume :: Float -> Float
volume radius = (4.0 / 3.0) * pi * (radius ^ 3)

area :: Float -> Float
area radius = 4 * pi * (radius ^ 2)
  • ディレクトリGeometryの下にSphere.hsを置いたので、Geometry.Sphere

8.Making Our Own Types and Typeclasses

Algebraic data types intro

data Bool = False | True

data Point = Point Float Float deriving (Show)
data Shape = Circle Point Float | Rectangle Point Point deriving (Show)

surface :: Shape -> Float
surface (Circle _ r) = pi * r ^ 2
surface (Rectangle (Point x1 y1) (Point x2 y2)) = (abs $ x2 - x1) * (abs $ y2 - y1)
  • =の後ろが値コンストラクタ
  • 値コンストラクタは実は関数(引数を取れる)
  • derivingで、型クラスのインスタンスとする
  • derivingが使えるのはEq、Ord、Show、Readのみ
  • 値コンストラクタが1つだけの場合、型名と同じ関数名にするのが慣習
  • 関数のパターンマッチの対象は、実は値コンストラクタだった
ghci> :t Circle
Circle :: Point -> Float -> Shape
ghci> surface (Circle (Point 0 0) 24)
1809.5574
ghci> map (Circle (Point 10 20)) [4,5,6]
[Circle (Point 10.0 20.0) 4.0,Circle (Point 10.0 20.0) 5.0,Circle (Point 10.0 20.0) 6.0]
  • 値コンストラクタも、普通の関数のように使える
module Shapes 
( Point(..)
, Shape(..)
, surface
) where
  • 全ての値コンストラクタをexportするなら、..
  • Shape(Circle,Rectangle)と列挙しても良い

Record syntax

data Person = Person String String Int deriving (Show)

firstName :: Person -> String
firstName (Person firstname _ _) = firstname

data Person' = Person' { firstName' :: String
                     , lastName' :: String
                     , age' :: Int
                     } deriving (Show)
  • {}で囲む
  • フィールド名、ダブルコロン、型
  • フィールド名と同じ名前のgetter関数が自動的に定義される
ghci> let guy = Person "Buddy" "Finklestein" 43
ghci> firstName guy
"Buddy"
ghci> let guy2 = Person' "Buddy" "Finklestein" 43
ghci> let guy3 = Person' {age'=24, firstName'="Martin", lastName'="Sheen"}
ghci> firstName' guy2
"Buddy"
ghci> age' guy3
24
ghci> guy
Person "Buddy" "Finklestein" 43
ghci> guy2
Person' {firstName' = "Buddy", lastName' = "Finklestein", age' = 43}
ghci> guy3
Person' {firstName' = "Martin", lastName' = "Sheen", age' = 24}
  • ハッシュみたいな感じで値を作れる

Type parameters

data Maybe a = Nothing | Just a

data Vector a = Vector a a a deriving (Show)
vplus :: (Num t) => Vector t -> Vector t -> Vector t
(Vector i j k) `vplus` (Vector l m n) = Vector (i+l) (j+m) (k+n)
  • Maybe aのaは型引数
  • Maybeは具象な型ではなく、型コンストラクタ
  • 引数を与えられて初めてMaybe Char、Maybe Personなどの具象な型になる
  • 型コンストラクタも関数だが、引数には型クラス制約を付けないのが慣例
ghci> :t Nothing
Nothing :: Maybe a
ghci> :t Just 1
Just 1 :: Num a => Maybe a
ghci> :t Just 1 :: Maybe Int
Just 1 :: Maybe Int :: Maybe Int

ghci> Vector 3 5 8 `vplus` Vector 9 2 8
Vector 12 7 16

Derived instances

data Person = Person { firstName :: String
                     , lastName :: String
                     , age :: Int
                     } deriving (Eq, Show, Read)
data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday 
           deriving (Eq, Ord, Show, Read, Bounded, Enum)
  • derivingで型クラスを指定
  • ただし各フィールドが、その型クラスのインスタンスであること
ghci> read "Person {firstName =\"Michael\", lastName =\"Diamond\", age = 43}" :: Person
Person {firstName = "Michael", lastName = "Diamond", age = 43}
ghci> Saturday > Friday
True
ghci> minBound :: Day
Monday
ghci> succ Monday
Tuesday
ghci> [Thursday .. Sunday]
[Thursday,Friday,Saturday,Sunday]
ghci> read "Just 't'" :: Maybe Char
Just 't'
  • Ordインスタンスでは、先に定義された方が小さいと見なされる

Type synonyms

type String = [Char]

type PhoneNumber = String
type Name = String
type PhoneBook = [(Name,PhoneNumber)]

inPhoneBook :: Name -> PhoneNumber -> PhoneBook -> Bool
inPhoneBook name pnumber pbook = (name,pnumber) `elem` pbook

type IntMap v = Data.Map.Map Int v
type IntMap' = Data.Map.Map Int
  • 既存の型に別名を与える
  • 既存の型を基に、型コンストラクタを定義することもできる
  • 部分適用スタイルでもOK
data LockerState = Taken | Free deriving (Show, Eq)
type Code = String
type LockerMap = Data.Map.Map Int (LockerState, Code)
lockerLookup :: Int -> LockerMap -> Either String Code
lockerLookup lockerNumber map = 
    case Data.Map.lookup lockerNumber map of 
        Nothing -> Left $ "Locker number " ++ show lockerNumber ++ " doesn't exist!"
        Just (state, code) -> if state /= Taken 
                                then Right code
                                else Left $ "Locker " ++ show lockerNumber ++ " is already taken!"

lockers :: LockerMap
lockers = Data.Map.fromList
    [(100,(Taken,"ZD39I"))
    ,(101,(Free,"JAH3I"))
    ,(103,(Free,"IQSA9"))
    ,(105,(Free,"QOTSA"))
    ,(109,(Taken,"893JJ"))
    ,(110,(Taken,"99292"))
    ]
  • 正常終了なら結果を、異常終了ならエラー内容を返すような関数には、Eitherを使うと便利
  • Eitherは、LeftとRight、2つの値コンストラクタを持つ
  • Leftはエラーの場合、Rightは成功の場合に使う
ghci> lockerLookup 101 lockers
Right "JAH3I"
ghci> lockerLookup 100 lockers
Left "Locker 100 is already taken!"
ghci> lockerLookup 102 lockers
Left "Locker number 102 doesn't exist!"

Recursive data structures

data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)
  • リストを代数的に定義
  • Consは値コンストラクタ
ghci> Empty
Empty
ghci> 5 `Cons` Empty
Cons 5 Empty
ghci> 4 `Cons` (5 `Cons` Empty)
Cons 4 (Cons 5 Empty)
  • [4, 5]を4:(5:[])と書けるのと同じ
infixr 5 :-:
data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord)
  • Consを :-: に置き換える
  • 今度は、:-:が値コンストラクタ
  • infixr 5で、右結合の優先度5の演算子
  • 関数名が記号のみから成るので、デフォルトで中置
ghci> 3 :-: 4 :-: 5 :-: Empty
(:-:) 3 ((:-:) 4 ((:-:) 5 Empty))
  • showは、前置スタイルで書式化する
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right) 
    | x == a = Node x left right
    | x < a  = Node a (treeInsert x left) right
    | x > a  = Node a left (treeInsert x right)

treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
    | x == a = True
    | x < a  = treeElem x left
    | x > a  = treeElem x right
  • 2進木
ghci> let nums = [8,6,4,1,7,3,5]
ghci> let numsTree = foldr treeInsert EmptyTree nums
ghci> numsTree
Node 5 (Node 3 (Node 1 EmptyTree EmptyTree) (Node 4 EmptyTree EmptyTree)) (Node 7 (Node 6 EmptyTree EmptyTree) (Node 8 EmptyTree EmptyTree))
ghci> 8 `treeElem` numsTree
True
ghci> 100 `treeElem` numsTree
False

Typeclasses 102

class Eq a where
    (==) :: a -> a -> Bool
    (/=) :: a -> a -> Bool
    x == y = not (x /= y)
    x /= y = not (x == y)
  • 型クラスには、そのインスタンスがサポートすべき関数のインターフェイスを定義
  • デフォルト実装はオプション
  • ここでは定義が循環しているので、Eqのインスタンスは、==か/=のどちらかをオーバーライドする
  • 型引数の名前は小文字とする
  • Eqは、aとして具象型を要求している
  • Functor(後述)のように、型コンストラクタを要求する型クラスもある
data TrafficLight = Red | Yellow | Green

instance Eq TrafficLight where
    Red == Red = True
    Green == Green = True
    Yellow == Yellow = True
    _ == _ = False

instance Show TrafficLight where
    show Red = "Red light"
    show Yellow = "Yellow light"
    show Green = "Green light"
  • 型TrafficLightを、型クラスEqのインスタンスとする
  • derivingと違い、インターフェイスの実装も与える
  • この場合、Eqが実装済みの==をオーバーライドしていることになる
  • /=は==を使って実装済みなので、/=をオーバーライドする必要は無い
ghci> :info Num
class (Eq a, Show a) => Num a where
  (+) :: a -> a -> a
  (*) :: a -> a -> a
  (-) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a
        -- Defined in GHC.Num
instance Num Integer -- Defined in GHC.Num
instance Num Int -- Defined in GHC.Num
instance Num Float -- Defined in GHC.Float
instance Num Double -- Defined in GHC.Float
  • 定義する型クラスに型クラス制約を付けることは、サブクラスを定義するようなもの
instance (Eq m) => Eq (Maybe m) where
    Just x == Just y = x == y
    Nothing == Nothing = True
    _ == _ = False
  • Maybe自体は型コンストラクタなので、Eqのインスタンスにはできない
  • Maybeが作る具象クラスなら、Eqのインスタンスとすることができる
  • Maybeの中身同士の==を使いたいので、型クラス制約(Eq m)が必要

A yes-no typeclass

class YesNo a where
    yesno :: a -> Bool

instance YesNo Int where
    yesno 0 = False
    yesno _ = True

instance YesNo [a] where
    yesno [] = False
    yesno _ = True

instance YesNo Bool where
    yesno = id

yesnoIf :: (YesNo y) => y -> a -> a -> a
yesnoIf yesnoVal yesResult noResult = if yesno yesnoVal then yesResult else noResult
  • idは、引数をそのまま返す関数
ghci> yesno $ length []
False
ghci> yesno "haha"
True
ghci> yesno True
True
ghci> yesnoIf [] "YEAH!" "NO!"
"NO!"

The Functor typeclass

ghci> :info Functor
class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (GHC.Base.<$) :: a -> f b -> f a
        -- Defined in GHC.Base
instance Functor (Either a) -- Defined in Control.Monad.Instances
instance Functor ((->) r) -- Defined in Control.Monad.Instances
instance Functor ((,) a) -- Defined in Control.Monad.Instances
instance Functor (Map k) -- Defined in Data.Map
instance Functor Maybe -- Defined in Data.Maybe
instance Functor [] -- Defined in GHC.Base
instance Functor IO -- Defined in GHC.Base
  • Functorの型引数fは、具象型ではなく、型コンストラクタ
  • fmapの型宣言でf aのように使われていることから、そう推論できる
instance Functor [] where
    fmap = map

instance Functor Maybe where
    fmap f (Just x) = Just (f x)
    fmap f Nothing = Nothing
  • リストはFunctorのインスタンス
  • ここの[]は、空リストではなく、「何かのリスト」という意味
  • ☆なぜか、[a]とは書かない
ghci> fmap length (Just "abc")
Just 3
  • Maybe StringがMaybe Intに変わった
  • Maybeの中身を取り出すことなく、中身に関数lengthを適用できる
  • ☆mapというと繰り返しを連想するが、繰り返しを伴わないmapもあるのだ

Kinds and some type-foo

ghci> :k Int
Int :: *
ghci> :k Maybe Int
Maybe Int :: *
ghci> :k Maybe
Maybe :: * -> *
  • IntやMaybe Intは具象型
  • Maybeは具象型を型引数に取り、具象型を返す、型コンストラクタ
ghci> :k Either
Either :: * -> * -> *
ghci> :k Either String
Either String :: * -> *
  • 関数のように、部分適用もあり
  • MaybeやEither Stringは、Functorのインスタンスにできる
  • Functorが引数に取るのは、種が* -> *の型コンストラクタである
class Tofu t where
    tofu :: j a -> t a j
  • j aは関数tohuの引数なので、種は*のはず
  • よって、jの種は* -> *で、aの種は*だろう
  • つまり、tの種は* -> (* -> *) -> *
  • 具象型を見つけて、そこから高階に上っていきながら、各型の種を推論する
data Frank a j  = Frank {frankField :: j a} deriving (Show)
  • ADT(☆Abstract Data Type? ここではRecord Syntaxのこと?)のフィールドは具象型のはず
  • よってj aの種は*
  • aの種は*、jは* -> *
  • よって型Frankの種は、* -> (* -> *) -> *
  • つまり、Tofuのインスタンスにピッタリ
instance Tofu Frank where
    tofu x = Frank x
  • tがFrank
  • tofuの引数はj a
  • frankFieldの型もj a
  • 例えば、tofu (Just "a")は、Frank (Just "a")
ghci> tofu (Just "a") :: Frank [Char] Maybe
Frank {frankField = Just "a"}
  • 型注釈によりFrank用のtofuを適用させる
data Barry t k p = Barry { yabba :: p, dabba :: t k }
  • pは*
  • tは* -> *
  • kは*
  • Barryは、(* -> *) -> * -> * -> *
  • Barryをtとkへ部分適用すれば、* -> *になり、Functorのインスタンスにピッタリ
  • 関数fmapは、Barryのpを取り出すことなく、何かの関数を適用する
class Functor f where
  fmap :: (a -> b) -> f a -> f b

instance Functor (Barry t k) where
    fmap f (Barry {yabba = x, dabba = y}) = Barry {yabba = f x, dabba = y}
  • xもf xも、yabbaの値なのでp型
  • つまり、fの型は、a -> aのはず

お疲れ様です。Part2へ続きます。

Last modified:2012/11/27 16:49:37
Keyword(s):
References:[FP: 関数型プログラミング] [LYAHFGG!まとめ(リファレンス)] [LYAHFGG!まとめ(Part2)]
This page is frozen.