Haskell
https://images-fe.ssl-images-amazon.com/images/I/51eiKJEossL._SY346_.jpg
Motivation
関数型の概念を知っておくと活かせることがありそうだったので。主に Parser 書こうと思ったら概念にぶつかったので、以前途中まで読んで放置していたすごい H 本を再読することに。今読むと割とわかることが多かったりする。 概要
GHCの準備
GHCとは?
GHC (Tha Glasgow Haskell Compiler) は、Haskell コンパイラの中でも広く使われているもの。Haskell コード (.hs) をコンパイルできることに加えて、対話環境も備えている。 どう使うのか?
対話環境 (GHCi) は ghci コマンドで開始する。
code:console
$ ghci
: を入力すると、GHCi コマンドを入力できる。
table:コマンド
コマンド 意味
:quit (:q) 対話モードの終了
:l <file name> ファイルのロード
:r 現在のスクリプトをロード
型
ビルトインの基本的な型
他の言語にもあるような基本的な型がある。
Int, Float, Double, Bool, Char, String, ...
その他にもよく使われるデータ構造がある。とても重要なのだが、読み返したらわかる範疇なので、気が向いたらちょっとまとめたいな、くらい。
リスト
タプル(ペア, トリプル)
WIP: 型定義の見方について書く
関数の見え方
型制約の見え方
型変数もここで話す?
型を定義する (値コンストラクタ, レコード構文)
Haskell における型定義 は、型名と取り得る値の定義から構成され、data キーワードを用いて定義される。例えば、Bool 型の定義は以下のようになる。 code:.hs
data Bool = False | True
この時の 取り得る値の定義 は値コンストラクタと呼ばれる。値コンストラクタ とは、その名の通り結果として値を返すコンストラクタと捉えることができる。
例えば、図形を表現する型 Shape を定義し、さらにその値として Circle と Square の2つを定義したい。Circle は、xy座標と半径という 3 つの Float 値から構成される。Square は左上と右下のxy座標という 4 つの Float 値から構成される。この定義は、以下のように記述できる。
code:.hs
data Shaper = Circle Float Float Float |
Square Float Float Flaot Float
ある型 T の値コンストラクタは、0ないし複数の引数をとって最終的に型 T の値を返す関数 = コンストラクタと言える。
実際に型定義を確認してみる。型定義を確認したいときは、:t を利用する。確認してみると、Circle も Square も、どちらも Float を引数に取り、最終的に Shape 型の値を返す関数としての型を持つ。
code:.hs
Prelude> :t Circle
Circle :: Float -> Float -> Float -> Shape
Prelude> :t Circle 10.0 12.0 5.0
Circle 10.0 12.0 5.0 :: Shape
ここで、Bool の定義に立ち返ってみる。Bool の取り得る True も False も 値コンストラクタ だが、引数を1つも取らない。このように、引数を1つも取らない関数はHaskellでは「名前」あるいは「定義」と呼ばれる。 code:.hs
data Bool = False | True
Prelude> :t True
True :: Bool
すでに見た通り、値コンストラクタ のフィールド定義はわかりづらい。これをわかりやすくする構文として、レコード構文 がある。
code:.hs
-— レコード構文を使わない場合
data Person = Person String String
-— レコード構文
data Person = Person { firstName :: String
, lastName :: String }
型コンストラクタ, 型変数
型コンストラクタ とは、型を引数にとって新しい型を作る型のこと。List や Tuple、Maybe などが該当する。この時引数にとる型は、型変数 だとか 型引数 だとか言われる。型変数 は「どんな型も取り得る」ということを示すためのプレースホルダーのような役割を持つ。
code:.hs
data Maybe a = Nothing | Just a
注意点としては、型コンストラクタ自体は型ではない。例えば、単なる List や単なる Maybe という型は存在できない。ただし、List[Bool] や List[Integer] 等と同様に 多相的な型 List[a] を扱うことはできる。 code:.hs
-- Char を格納した List の型は、Char型のList となる
-- Bool を格納した List の型は、Bool型のList となる
-- では、空配列の型はどうなる?
-- 空配列の型は、任意の型aのListとなる
Prelude> :t []
-- [] はaの位置の型がなんであれ処理できるので、任意の型のリストと問題なく連結できる
-- ちなみに、Maybe型における Nothing も似たような定義になっている
Prelude> :t Nothing
Nothing :: Maybe a
型クラス
型クラス とは、関数の集合とともに定義されるものであり、ある型が取り得る振る舞い (関数) の集まりを定義している。ある型クラスのインスタンスである具体的な型は、型クラスに定義された振る舞いの実装をもつ。型クラスの定義の一部である関数は、型クラスのメソッドとも呼ばれる。上記で示した + や - 等のオペレータも、Haskell ではこの 型クラスのメソッド として定義されていて、Int や Float はこの型クラスのインスタンスであるため、これらを利用できる。 試しに、== の型を確認してみる。
code:.hs
ghci> :t (==)
(==) :: (Eq a) => a > a > Bool
=> よりも前にあるのは 型クラス制約 と呼ばれ、型定義内の値 a の型は Eq 型クラスのインスタンスである必要がある、ということを表している。
code:.hs
-- Eq: 等価性をテストできる型クラス
Prelude> :t (+)
(+) :: Num a => a -> a -> a
-- Ord: 順序をつけられる型クラス
Prelude> :t (<)
(<) :: Ord a => a -> a -> Bool
-- Show: 文字列として表現できる型クラス
Prelude> :t print
print :: Show a => a -> IO ()
型クラスの定義には、class キーワードを利用する。
code:.hs
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
x == y = not (x /= y)
x /= y = not (x == y)
-- サブクラス化
-- Num の型クラス宣言は、以下のようになっている
-- すなわち、aがEq型クラスのインスタンスであることを定義しているので、実質サブクラス、となる
class (Eq a) => Num a where
...
型クラスのインスタンス宣言
型クラスの定義では、メソッドの型定義や制約は示されるが、その振る舞いは示されない。もっというと、型クラスの定義では、型の値は考慮されない。が、関数を実行するためには、"その型の値" に対して関数がどう振る舞うか?を定義する必要がある。なので、型クラスのインスタンス宣言では、型クラスのメソッドの定義に対して、型がどの値をとったときにどのような結果を返すか?を網羅的に定義する必要がある。
型自体の宣言と、型クラスのインスタンス宣言は別々にできる。このように、Haskell では、型クラスであらかじめ型に適用可能な性質を記述しておき、後から特定の型をその型クラスのインスタンスとして宣言することで、型にその性質を付与することができる。 code:.hs
-- 信号機型. 赤,黄,緑 の3つの名前を値として持つ
data TrafficLight = Red | Yellow | Green
-- Eq 型クラスのインスタンス宣言
instance Eq TrafficLight where
(==) Red Red = True
(==) Green Green = True
(==) Yellow Yellow = True
_ == _ = False
-- Show 型クラスのインスタンス宣言
instance Show TrafficLight where
show Red = "Red light"
show Yellow = "Yellow light"
show Green = "Green light"
-- Eq 型クラスのインスタンスなので、== が利用できる
print $ Red == Red -- True
print $ Red == Green -- False
-- Show 型クラスのインスタンスなので、print が利用できる
print Red -- "Red light"
多相型、すなわち 型変数をとるような型コンストラクタのインスタンス宣言はどうするか?という問題がある。既述の通り、型コンストラクタは型ではないため、以下のように書くことはできない。 code:.hs
instance Maybe where
show ...
そのため、多相型の場合は、型変数もインスタンス宣言に含んで記述する。 code:.hs
-- 下記の定義では、Maybeの型引数aがEq型クラスのインスタンスである必要があるので、型制約をつけている
instance (Eq a) => Eq (Maybe a) where
Just x == Just y = x == y
Nothing == Nothing = True
_ == _ = False
その他、型クラスに関する参考記事を示しておく。
型インスタンスの自動導出
ある型をある型クラスのインスタンスにしたい場合は、その型クラスのインスタンスとして instance キーワードを用いてインスタンス宣言する必要がある。Haskell には、これを自動導出 (derive) する能力があり、一部の実用的な型クラスについては、そのインスタンス宣言を省略できる。これが利用できる型クラスは、Eq, Ord, Enum, Bounded, Show, Read。 code:.hs
-- 自動導出を使わない場合は、自分で宣言する必要がある
data Person = Person { firstName :: String
, lastName :: String }
instance Show Person where
show Person = "Person {firstName =..., lastName = ...}"
-- 自動導出を使う場合、宣言の必要はなく、Haskell に任せることができる
data Person = Person { firstName :: String
, lastName :: String } deriving (Show)
型シノニム
型シノニム は、同値で交換可能な型 を定義するのに利用される。例えば、[Char] と String がこの関係にあたる。型シノニム自体はエイリアスのようなもので、特に何もせず、可読性を向上させるくらい。
code:.hs
関数
関数定義 (型宣言, パターンマッチ)
関数定義の際には、予め 明示的な型宣言 をしておき、その後に具体的な定義を追加することができる。この書き方は、Haskell において良い慣習とされているらしい。 code:.hs
myFunc x = x + x
myFunc 10
-- 型定義を見たい場合は :t
Prelude> :t myFunc
myFunc :: Num a => a -> a
-- 明示的な型宣言
myFunc :: Num a => a -> a
myFunc x = x + x
関数の型だけ見てもその振る舞いは分からないので、振る舞いを知るためには実際の定義を見る必要があるのだが、この振る舞いをより柔軟に表現する記法として パターンマッチ がある。
code:.hs
-- 上から順に定義が評価されていき、最初にマッチした関数が実行される
lucky :: Int -> String
lucky 7 = "7"
lucky x = "not 7"
lucky 7 -- "7"
lucky 10 -- "not 7"
Haskell において、関数呼び出しは、その引数となる値に対して関数を 適用する という言い方をする。 code:.hs
-- === 関数呼び出し ===
-- 計算に利用する基本的なオペレータは中置記法を用いる
2 + 3
4 == 4
4 /= 6
-- 殆どの関数は前置記法を用いる
div 10 2
-- バッククオートで囲むと、中置記法にできる
10 dev 2
カリー化
Haskell の全ての関数は、公式には引数を1つだけ取ることになっている。引数を複数とっているように見える関数は、カリー化 されている。
code:.hs
Prelude> max 1 3
3
Prelude> max 10 6
10
Prelude> :t max
max :: Ord a => a -> a -> a
max の型定義は、max :: (Ord a) => a -> (a -> a) のようにも書ける。つまり、以下の2つのどちらとも取れる。
型 a の引数を 2 つとって、 型 a の戻り値を返す
型 a の引数を 1 つとって、 「型 a の引数を1つとって型 a の戻り値を返す」関数を返す
この時返される関数は、元の関数に引数を適用した結果得られる関数で、このような適用は 部分適用 と呼ばれる
code:.hs
Prelude> :t max
max :: Ord a => a -> a -> a
Prelude> :t max 3
max 3 :: (Ord a, Num a) => a -> a
Prelude> :t max 3 4
max 3 4 :: (Ord a, Num a) => a
部分適用 によって、新たな関数を作り、それをまた別の関数に受け渡すことができるようになる。
高階関数
関数を引数にとる、というのを型で表現すると、以下のようになる。ここでの () は省略できない。型定義内の () は、その部分が関数で置き換わることを示している。つまり、下記の関数は、引数を取り同じ型の返り値を返す関数を引数にとる、ということが示されている。
code:.hs
Prelude> applyTwice f x = f (f x)
Prelude> :t applyTwice
applyTwice :: (t -> t) -> t -> t
ラムダ式
1回だけ必要な関数を作るときに使う無名関数。\ を用いて書く。
code:.hs
Prelude> :t \x -> x + 3
\x -> x + 3 :: Num a => a -> a
関数適用
$ の右側の式を、左側の関数に適用する。これは、関数の適用を括弧なしにシンプルに記述するのに用いられるようだ。
code:.hs
Prelude> :t ($)
($) :: (a -> b) -> a -> b
通常、スペースを開けると、スペースの右側の式が左側の関数に適用される。つまり、左結合である。例えば、f a b c は ((f a) b) c を意味する。
一方、$ を用いた関数結合は右適用になる。つまり、$ の左側の式が、右側の関数に適用される。例えば、sqrt 3 + 4 + 9 は、sqrt に 3 が左結合されて、それに 4 と 5 が足し算される。先に右側の 3 + 4 + 5 を実行してもらいたい場合は、括弧で囲む必要がある (sqrt (3 + 4 + 5))。ここで $ を使うと、sqrt $ 3 + 4 + 5 のようにシンプルに記述できる。
関数合成
数学では、関数合成は $ (f \circ g)(x)=f(g(x))のように定義できる。Haskell の場合、. を使って関数合成ができる。
code:.hs
Prelude> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
再帰
WIP
有名な型クラス
型クラス とは、型に対する抽象的なインタフェースであり、型が持つ特徴そのものとも言える。ある型クラスのインスタンスとなる型は、その型クラスの定義する関数 (メソッド) を実行できる。言い方を変えると、その型クラスのインスタンスである型は、型クラスのメソッドを適用可能になる。このように、型クラスは、ある種の特徴的な振る舞いを型に付与する, あるいは振る舞いを適用可能にする 役割を持つ。
Functor
Functor は、全体を移す(map over)ことができる、という性質を型に付与する型クラス。その定義するメソッドは以下。
code:.hs
class Functor f where
fmap :: (a -> b) -> f a -> f b
定義されているメソッドは fmap 1つのみである。このメソッドのポイントは2つある。
高階関数 であり、関数 (a -> b) を引数にとる
f は 型コンストラクタである
型コンストラクタ とは、例えば List や Maybe 等、型変数 をとって初めて具体型となるような型のこと
f a や f b における a,b は各々 型変数
つまり、Functor は、型 a から b に変換する関数 (a -> b) と、型 a を引数にとるコンストラクタ f f a を与えると、型 b を引数にとる型 f b を取得できる。これは、型コンストラクタ f に覆われた型 a, b に対し、a -> b に変換する関数を与えると、f a -> f b のように、型コンストラクタ f を引き継いだまま関数を適用できる、とも言い換えられる。
具体例を見ていく。例えば、map は Functor である。
code:.hs
-- 「a -> b となる関数を渡して、さらに a を渡すと、最終的に b として結果が取得できる」 Prelude> :t map
map :: (a -> b) -> a -> b map _ [] = []
map f (x:xs) = f x : map f xs
つまり、Functor とは、とある型クラス f の中にある型を、ある変換用の関数を1つ与えるによって、型クラスの内部に閉じ込めたまま変換を適用できる ような性質を示している。
この、型クラスの内部に閉じ込めたまま 適用できる、というのが重要な意味を持っていて、専門用語だとこれは 文脈を維持したまま とも言い換えられる。では、型クラス、すなわち保たれる文脈にはどのようなものがあるか?見ていく。
List ([a]) 型コンストラクタ
複数の値を同時にとるかもしれない という文脈を保持する
Maybe (Maybe a) 型コンストラクタ
失敗するかもしれない計算 という文脈を保持する
関数 ((->) a) 型コンストラクタ
関数の型定義は a -> b のようにかけるが、これは (->) a b と書き換えられ、a を具体型として扱うと、これは (->) a という、型引数を1つとる型コンストラクタと扱うことができる
これは、型 a の引数が与えられると必ず何らかの型で値が返される という文脈を保持する
IO
副作用を伴う計算 という文脈を保持する
文脈を維持するということは、型コンストラクタを維持するということになる。そして、型コンストラクタはそれ自体が様々な振る舞い、特徴、性質を持つ。例えば、List は複数の同じ型の値を保持できるし、Maybe は値を持つことも持たないこともできる。ここで、具体的な値に何らかの変換処理を行いたい場合、手続き型であれば各型コンストラクタから具体型を引き出して関数を適用できる。一方で、Functor は、このような関数の適用の手順を、抽象的な操作としてあらかじめ定義しておくことで、型コンストラクタがどのような具体的な値をとっても安全に関数の適用ができるようになっている。
(うまく利点を説明できないので、WIP.....)
Applicative Functor
Applicative Functor は、文脈を維持したまま関数を合成していくことができる?みたいな感じ?
Functor を適用してその結果が文脈の中に入り込むと、それを取り出してさらに利用するのが難しいが、Applicative Functor は文脈を維持したまま計算し続けられる、イメージ
code:.hs
class (Functor f) => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
Monad
Monad は、文脈を付与された関数を、文脈が付与されていない型から付与されていない型に変換する関数に入力し、文脈を付与された型を返す。実際に文脈を付与する、と言った場合、例えばわかりやすいのは、「ある処理をして、それが失敗あるいは成功する」みたいな場合、入力時点では文脈がなく、出力時に文脈が付与される。そして、その結果をさらに他の同様の関数にも適用したい場合には、その時の文脈の性質を持っている必要がある。
code:.hs
class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
x >> y = x >>= _ -> y
fail :: String -> m a
fail msg = error msg
このように、モナドの性質を持つ型クラスあるいは型コンストラクタは、「計算前には付与されていないが、計算後に文脈を付与するような関数」に対して、「文脈が付与された値」を適用できる。その結果、そのような関数を繰り返し適用しても、文脈を維持し続けることができる。
List<a> -> (a -> List<b>) -> List<b>
[1,2,3].flatMap(x -> [x, x*2]) => [1,2,2,4,3,6]
List<List<r>> -> (List<r> -> List<b>) -> List<b>
[[1,2],[3]].flatMap(x -> x) => [1,2,3]
(a -> b) -> List<a> -> List<b>
[1,2,3].map(x -> x*2) => [2,3,4]