Zenn
Closed26

速習Haskell

Haskell
ぱんだぱんだ

Get Started

https://www.haskell.org/get-started/#set-up-a-haskell-development-environment

setup

  • HaskellのセットアップにはとりあえずGHCupをインストールすれば良さそう
  • GHCupをインストールするとHaskellでプログラミングするのに必要な以下のツールがインストールされる
    • GHC Haskellのコンパイラ。実際はCabalやStackのようなツールを使ってビルドすることがほとんど
    • HLS HaskellのLanguage Server。これはインストールしなくてもVSCodeのHaskell拡張などを使うときには裏で勝手に使ってくれるのでインストールしなくても良いらしい
    • Cabal Haskellプロジェクトの構成、ビルド、実行、依存関係の定義などをやってくれるツール。
    • Stack Cabalと同等のツール。Cabalかどっちかがあればいいらしいがどっちも入れておけばどっちで構成されたHaskellプロジェクトにも対応できる。GHCupのインストールでどっちも入る。

GHCupは以下のコマンドでインストールできる

curl --proto '=https' --tlsv1.2 -sSf https://get-ghcup.haskell.org | sh

上記のコマンドを実行するといくつか対話形式で聞かれる。

  • .zshrcなどにPATHの記載を自動でするか
  • HLSをインストールするか
  • StackでGHCをインストールする際にGHCupを使うような連携機能を有効にするかどうか

ここら辺は以下の記事がとても詳しく書いてある

https://zenn.dev/mod_poppo/articles/haskell-setup-2023#stackを使う

StackはデフォルトでGHCをプロジェクト単位でインストールするが、GHCupですでにインストールされている場合、無駄に容量を使ってしまうので以下の設定をしておくことでシステムのGHCを使い無駄にインストールすることを防げるらしい。

stack config set install-ghc false --global
stack config set system-ghc true --global

あとはVSCodeの拡張をインストールしておく

https://marketplace.visualstudio.com/items?itemName=haskell.haskell

ghciでプログラムを実行してみる

ghciというインタラクティブにHaskellコードを実行できるコマンドがインストールされているはずなので実行してみる

ghci

ghci> 1 + 1
2
ghci> take 10 (filter even [43..])
[44,46,48,50,52,54,56,58,60,62]
ghci> sum it
530

Haskellのプログラムを書いてみる

以下のようにhello.hsファイルを作成しプログラムを書いてみる

hello.hs
main = do
  putStrLn "Hello, World!!"
  putStrLn ("odd number" ++ show (filter odd [10 .. 20]))

コンパイルと実行は以下

ghc hello.hs
./hello

Hello, World!!
odd number[11,13,15,17,19]

ghciにファイルを直接ロードして関数を実行することもできる

ghci hello.hs

ghci> main
Hello, World!!
odd number[11,13,15,17,19]
ぱんだぱんだ

Hello World

とりあえずHaskellでHello Worldは以下のような感じ

main = do
  putStrLn "Hello, World!!"

main関数の定義がHaskellのエントリーポイント

doについて

doはIOなどのモナドを扱うためのシンタックスシュガー。見た目は手続き型プログラミングのように処理を順に書けるが純粋関数型プログラミングの原則を破るものではない。

doブロックの最後の式が最終的な型となり、do記法の中の式は全て同じモナド型である必要がある。

ぱんだぱんだ

変数と束縛

関数型プログラミングの世界では変数への代入が存在しない。代わりに束縛というワードが登場する。なんで変数じゃだめなのとか素人質問をしたくなるが変数とは値を格納する箱のイメージで実際にメモリ位置への参照をもっていたりする。これは参照透過性や不変性を扱う純粋関数型プログラミングにとって嬉しくないのでより数学的に式を表現するために変数という概念を用いていないと理解。

束縛は値を格納するのではなく値の関係を定義する。

let x = 5
    y = x + 1

上記の例ではｘは5であるという関係を定義していることになる。

letの基本は以下

-- 基本形式
let 束縛 in 式

-- 例
let x = 5 in x + x  -- 結果: 10

ただし、doブロックの中ではinは省略できる

ぱんだぱんだ

関数シグネチャ

double x = x + xのように宣言した関数の関数シグネチャはdouble :: Num a => a -> aとなる。

これは<関数名>::<型制約>=><関数シグネチャ>みたいになる。型の制限はNum aの部分でNum型に含まれる型(IntやFloatなど)に型を絞っている。

ちなみにこの関数の型はHaskellコンパイラが型推論したもので以下のようにすれば型を明示的に示せるが型推論に任せてしまったほうが汎用性の高い関数になる。

double :: Int -> Int
double x = x + x
ぱんだぱんだ

ビルドと実行について

ghc hello.hs

上記でhaskellファイルをビルドすると前述したが、上記コマンドでビルドすると実行ファイルであるhello以外にhello.hiとhello.oという中間ファイルも生成される。これらの中間ファイルは実行ファイルを作る過程で生成されるもののため削除しても問題ないらしい。削除して問題ないのであればghcのオプションで出力を抑制できないのかと思ったらできるっぽい。

ただ、開発中にコードを実行するのであれば

runghc hello.hs
or
runhaskell hello.hs

で中間ファイルを作らず直接実行できる。

ぱんだぱんだ
qsort [] = []
qsort (x : xs) = qsort smaller ++ [x] ++ qsort larger
  where
    -- smaller = filter (< x) xs
    smaller = [a | a <- xs, a <= x]
    -- larger = filter (>= x) xs
    larger = [a | a <- xs, a > x]

上記のHaskellのプログラムについて。

  • 関数の処理として引数のリストをソートする
  • ++はリストを結合させる二項演算子
  • 引数のリストの最初の要素をx、残りをxsとしxより小さいリストと大きいリストを計算し、[x]と結合させることでソートしたリストが出来上がる
  • whereは中間結果に名前をつけられるHaskellの強力な構文
  • 上記の例だとxより小さい要素のリストをsmaller、大きい要素のリストをlargerと名前付けし計算に使うことができるため、可読性が向上する
  • where内の計算は2つ記載してあるが、一つはリスト内包表記と呼ばれるもの
    • [a|a <- xs, a <=x]とあった場合、xsの要素を順番にaに束縛しa <= xという条件にあったリストを作成する
  • コメントアウトしているパターンはfilter関数を使用して引数で指定した高階関数の条件に当てはまる要素に絞ったリストを作成する
  • リスト内包表記とfilterのどっちを使うかは好みによるっぽい
  • このqsortの関数シグネチャはqsort :: Ord a => [a] => [a]となり、順序比較できる値のリストであれば引数にとれる汎用的な関数となっている
  • 上記を特に型を明示することなくHaskellコンパイラの型推論のみで動くのがHaskellの型システムが強力と言われる特徴だろう
ぱんだぱんだ

型クラス

すでに出てきているがNumやOrdといったもの。これらは型ではなく型クラスと呼ばれる。他の言語にあるインターフェースと同じように特定の振る舞いを持つ型の集まりを表現することができる。

ぱんだぱんだ

BlockArguments拡張

main関数で登場したdo記法は改行とインデントでブロックをコンパイラが認識している。そのため、改行なしでdoブロックを書こうとするとコンパイルエラーが発生する。

この場合、$演算子を使うかBlock Arguments拡張を使用すればインラインでも書ける

main = do
  forever $ do putStrLn "Hello, World!!"

-- これをファイルの先頭に記載
{-# LANGUAGE BlockArguments #-}
ぱんだぱんだ

Haskellの型推論

以下のコードについて考える。

seqn [] = return []
seqn (act : acts) = do
  x <- act
  xs <- seqn acts
  return (x : xs)
  • この関数はリストで副作用を伴う処理を受け取り、実行した結果をリストで返す関数
  • この関数シグネチャはseqn :: Monad m => [m a] -> m[a]となる
  • この関数も汎用的で例えばseqn [getChar, getChar]のようにキーボードからの入力を何文字か受け入れることもできますし、その他のモナドを扱うこともできる

ちなみに

seqn [] = []

にすると明示的に関数シグネチャを書かないとうまく型推論が効かない。これはreturnが単に空のリストを返すだけではなくモナドを返すよということを明示する役割(単なる値ではなくモナドの文脈に持ち上げる)があるため。

ぱんだぱんだ

プレリュード

Haskellでは組み込みで用意されているモジュールをプレリュードと呼び、特にリストに関するプレリュードが多く提供されている。

head, take, reverseといった関数たち

ぱんだぱんだ

命名規則

Haskellではリストを表すときは複数形であることがわかりやすいように末尾にsをつけてxsやnsといったふうに表現することが多い

ぱんだぱんだ
avarage ns = sum ns `div` length ns
  • 上記のように引数を2つ取る関数はバッククォートで囲うことで引数の間に宣言することができる
  • Haskellではインデントで波括弧で囲われたブロックを表現するためインデントに問題を起こしやすいタブの使用は禁止されている
ぱんだぱんだ

型と型クラス

Haskellでは以下のようにして型を表現する

Fasle :: Bool
not :: Bool -> Bool
  • Falseという値は真理値の型である
  • notという関数はBoolを引数にBoolを返す
  • また、::は評価前の式にも利用できる
not False :: Bool
  • Haskellでは全ての式に型がつき、型推論によって式が評価される前に型が決定する
  • そのため、式が評価される前に型検査が実行され、型安全が保証される
  • 型検査が通ったとしてもエラーが絶対でないわけではない
  • 例えば0徐算などは型検査が通ったとしても評価時にエラーが出る代表的な例
  • 逆に式の評価自体は問題なくても型が合っていなければ型検査に引っかかる場合もある
-- これは常に1を返すので正しそうだがelseが真理値を返すため型が揃っておらず型エラーとなる
if True then 1 else False
  • Haskellの標準型は以下のようなものがあり他の一般的なプログラミング言語とだいたい同じような型となっている
    • Bool
    • Char
    • String
    • Int
    • Integer(多倍長整数)
    • Float
    • Double
    • リスト
    • タプル
    • 関数型
  • 関数は全域関数である必要はない
  • 全域関数とは全ての入力に対して出力が定義されている関数のこと
  • 例えばリストのプレリュード関数であるheadは空のリストに対して定義されていない
  • カリー化
    以下のような関数を考える
add :: (Int, Int) -> Int
add (x,y) = x + y

add' :: Int -> (Int -> Int)
add' x y = x + y
  • addはタプル型の引数を一つとりInt型の値を返す関数
  • add'はInt型の値を一つとりInt -> Intの関数を返す関数
  • add'の実装を見るとadd::Int->Int->Intなのになんでadd'::Int->(Int -> Int)で型付できるのかがピンとこない
  • この理解にはまずHaskellにおける関数が1つの引数を取り1つの値を返すということを理解しないといけない
  • add'は2つの引数をとっているが処理の流れ的には1つずつ引数を処理していっている
  • add' :: Int -> (Int -> Int)はまず1番左側のIntを引数に取りInt -> intの関数を返す。1つの引数で1つの値。
  • そして、返ってきた関数の引数にIntが適用されIntが最終的に戻り値として得られる
  • そのため、add'に一つだけ引数を与えてInt -> Intの関数を得ることもできる
  • これを部分適用と言い、このような性質を持つ関数をカリー化の性質を持つという
  • このカリー化の性質と部分適用は関数合成の際に重要な役割を果たすそう
  • 話を戻してadd'::Int -> Int -> Intとadd'::Int -> (Int -> Int)が同じ型を表すことの理解は引数を2つ取り1つの値を返す関数という理解から引数を一つ取り関数を返す、その関数にまた1つ引数を適用してIntの値を得る関数という理解に変える必要がある
  • カリー化された関数を扱うときに括弧が過剰になるのを防ぐために以下の2つの規則がある
    • 型の中の->は右結合
      • Int -> Int -> Int -> IntとInt ->(Int -> (Int -> Int))は同じ型を表します
    • 空白文字を用いて表す関数適用は左結合
      • mult x y zは((mult x) y) zとなる
  • 多相型
    • length関数のようにどのような型も取れるような関数の引数は型変数を含めることで定義できる
    • 具体的にはlength関数はlength :: [a] -> Int となる
    • 型変数は先頭は小文字である必要がある
    • 一つ以上の型変数を持つ型や式を多相的と呼び、lengthのような多相型を持つ関数を多相関数と呼ぶ
  • 多重定義型。前述しているが(+) :: Num a => a -> a -> aのような型シグネチャのNum aのような型制約のある型定義を多重定義型という。
  • 型制約に使う型クラスは基本クラスとして以下のようなものが用意されている
    • Eq
    • Ord
    • Show
    • Read
    • Num
    • Integral
    • Fractional
  • Numクラスは+や-といった演算子で計算できる型がインスタンスとなるが、徐算の演算子は含まれていないことに注意したい
  • 徐算の演算子/は分数クラスであるFractionalのインスタンスに用意されている。FractionalクラスのインスタンスにはDoubleやFloat型が含まれる
ぱんだぱんだ

関数定義

条件式

myabs :: Int -> Int
myabs n = if n >= 0 then n else -n
  • Haskellのifはelseの省略はできない
  • 入れ子にすることもできる

ガード付きの等式

signum1 :: Int -> Int
signum1 n =
  if n > 0
    then 1
    else
      if n == 0 then 0 else -1

signum2 :: Int -> Int
signum2 n
  | n > 0 = 1
  | n == 0 = 0
  | otherwise = -1
  • 上記のようにガード付き等式を使うと読みやすくなる
  • ガード付き等式は| n > 0 = 1で表現する
  • この条件式がTrueならこのガード付き等式の値が選択される。Falseなら次のガード付き等式が評価される
  • otherwiseを書くことで全ての条件式がFalseの時に選択される値を定義できる
  • otherwiseは必須ではない。otherwiseを省略して条件式が全てFalseとなる値を渡すとエラーとなる

パターンマッチ

myAnd :: Bool -> Bool -> Bool
myAnd True True = True
myAnd True False = False
myAnd False True = False
myAnd False False = False

Haskellにおけるパターンマッチは上記のような感じ。
上記の関数myAndを使うと以下のようになる。

ghci> myAnd True (1 + 1 == 2)
True
ghci> myAnd True (1 + 1 == 3)
False
ghci> myAnd False (1 + 1 == 2)
False
ghci> myAnd False (1 + 1 == 3)
False

ちゃんと網羅されている。ちなみに以下のようにパターン網羅しない場合、網羅できていない関数呼び出しをするとエラーになる。

myAnd :: Bool -> Bool -> Bool
myAnd True True = True
myAnd True False = False
myAnd False True = False
-- myAnd False False = False

パターンマッチにはワイルドカードがあり、myAndの実装は以下のように書ける

myAnd True True = True
myAnd _ _ = False

Haskellのパターンマッチでは以下のようなタプルパターン、リストパターンといった便利な方法がある。

helloWorld :: (String, String) -> String
helloWorld ("Hello", "World") = "Hello World"
helloWorld _ = "Hello"

test :: [Int] -> Int
test [1, _, _] = 1
test _ = 0

Haskellにおけるリストは空の[]に::(cons演算子)で要素を先頭に追加していったものと考えられる。具体的には[1, 2, 3]は(1 :: (2 :: (3 :: [])))と同義である。

strHead :: [String] -> String
strHead [] = ""
strHead (x:_) = x

strTail :: [String] -> [String]
strTail [] = []
strTail (_:xs) = xs

strLast :: [String] -> String
strLast [] = ""
strLast [x] = x
strLast (_:xs) = strLast xs

cons演算子を使う場合、関数適用のほうが先に評価されるのでカッコで括る必要がある。

ラムダ式

odds :: Int -> [Int]
odds n = map (\x -> x * 2 + 1) [0..n-1]

こういうの

セクション

  • +のように引数の間に置かれる関数を演算子と言う
  • 関数型プログラミングの世界では演算子も関数として扱うのだなぁ
  • これは10 `div` 2のようにバッククォートで囲うことで引数を二つ取る関数を演算子として扱うこともできる
  • 逆も成り立って、(+)のように演算子をかっこで囲うことで引数の前に置いてカリー化された関数として扱うことができる
  • このように演算子をかっこで囲った(+)や(+ x)を引数xとyに対するセクションと呼ぶ
  • このセクションは以下の3つの利用方法がある
    • 単純な関数を極めて簡潔な形で定義することができる
    • 演算子の型宣言をするときに必要
    • foldlのような関数を引数として渡すときに二項演算子を引数として渡せる
  • 単純な関数とは例えば、\x -> (\y -> x + y)のような加算関数を(+)として表現できるということ
  • 演算子の型宣言は演算子そのものは完全な式ではないため(+) :: Int -> Int -> Intのようにセクションを使う必要がある
  • 二項演算子を引数に渡す例はsum = foldl (+) 0のような感じ
ぱんだぱんだ

リスト内包表記

main = do
  let f xs = [x ^ 2 | x <- xs]
  print (f [1, 2, 3])
  • 数学の世界で既存の集合から新しい集合を生成するのに内包表記が使える
  • Haskellの世界では既存のリストから新しいリストを生成するのにリスト内包表記が使える
  • |の右側は生成器と呼ぶ
  -- 生成器は複数記述可能
  let f' = [(x, y) | x <- [1..3], y <- [x..3]]
  print f'

  -- リストの要素はワイルドカードで捨てることもできる
  let length' xs = sum [1 | _ <- xs]
  print (length' [1, 2, 3])
  • ガードを使うと条件式で生成するリストの要素を絞ることができる
  -- ガードを使って偶数のリストを生成する
  -- ガードは条件式を記述することで、リストの要素を絞り込むことができる
  print ([x | x <- [1..10], even x])
  • zip関数とリスト内包表記は一緒に使われることが多い
  • zip関数は以下のように引数にリストを2つ取り、それぞれの要素を順番に組にした新しいリストを作る
  -- [('a',1),('b',2),('c',3)]
  print (zip ['a' .. 'c'] [1 .. 4])
  • zip関数とリスト内包表記を使った昇順ソートの判定関数
-- リストの隣り合う要素をペアにする
pairs :: [a] -> [(a, a)]
pairs xs = zip xs (tail xs)

-- リストが昇順にソートされているかどうかを判定する
sorted :: Ord a => [a] -> Bool
sorted xs = and [x <= y | (x, y) <- pairs xs]
  • 以下のpositions関数は指定の値が位置するリストのインデックスのリストを返す
-- リストの要素の位置を返す
positions :: Eq a => a -> [a] -> [Int]
positions x xs = [i | (y, i) <- zip xs [0..], x == y]
  • 上記のpositions関数のリスト内包表記の生成器で使われているzip関数の第二引数は無限のリストです
  • しかし、Haskellにおいて無限のリストは遅延評価されるため実際には第一引数の長さまでしか使用されません
  • 文字列StringはCharのリスト
  • "abc" :: Stringは['a', 'b', 'c'] :: [Char]と同義
ぱんだぱんだ

再帰関数

  • 階乗を計算するfac関数は以下のように数値のリストから積を計算するプレリュード関数であるproductを使って以下のように定義できる
fac :: Int -> Int
fac n = product [1..n]
  • これは再帰関数として以下のようにも定義できる
fac :: Int -> Int
fac 0 = 1
fac n = n * fac (n -1)
  • 最初の等式で0の階乗は1であることを定義していますがこれは再帰関数において基底部と呼ばれる
  • そして次の等式のfac (n-1)の部分は再帰部と呼ばれる
ぱんだぱんだ

高階関数

  • 既に学んだが以下は同じ意味
add :: Int -> Int -> Int
add x y = x + y

add :: Int -> (Int -> Int)
add = \x -> (\y -> x + y)
  • 下の定義はxを引数に取り、yを引数にxとyを加算して返す関数を返すという意味になる
  • 高階関数とは引数として関数を取る関数や返り値として関数を返す関数を表す
  • しかし、「返り値として関数を返す」ことを表現するカリー化という用語が定着しているため、前者の引数として関数を取る関数のことを高階関数として表現することが多い

畳込関数 foldr foldl

  • 引数にリストを取る関数の多くはリストに対する再帰を使って以下のように書けることが多い
f [] = v
f (x:xs) = x # f xs
  • 空のリストを引数に取ったときの値vを定義することで再帰の基底部とする
  • #は任意の演算子
  • 例えば、sum関数は以下のように再帰で定義できる
sum :: Num a => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs
  • この再帰を閉じ込めたプレリュード関数がfoldr
  • foldrの引数は演算子#と値v
  • 上記のsum関数はfoldrを使うと以下のように定義できる
sum :: Num a => [a] -> a
sum = foldr (+) 0

この定義は引数のリストを明示的に書くことで以下のようにも書ける

sum xs = foldr (+) 0 xs
  • しかし、部分適用を使って引数のリストを省略したほうが簡潔なので省略して書くことが多い(たぶん、コンパイラからも省略しなよって言われる)
  • 関数foldr自体は以下のように定義できる
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
  • 理解するには再帰で考えるよりcons演算子(::)で考えたほうが理解できるかもしれない
-- foldr (+) 0を[1, 2, 3]というリストに適用すると
1 : (2 : (3 : []))
  • cons演算子を演算子に、空のリストを初期値の0に置き換えると以下のようになる
1 + (2 + (3 + 0))
  • foldrのrはrightでこれは演算子が右結合で使われることを前提としていることに由来する
  • 後述のfoldlは逆に左結合を前提としている
  • 例えば、前述のsum関数は以下のようにも定義できる
sum :: Num a => [a] -> a
sum = sum' 0
    where
        sum' v [] = v
        sum' v (x:xs) = sum' (v+x) xs
  • このように定義すると加算演算子が左結合として計算されることになる
  • このような左結合を想定した式は以下のように定義できる
f v [] = v
f v (x:xs) = f (v # x) xs
  • #は任意の演算子でvを蓄積変数と呼ぶ
  • 蓄積変数とリストの先頭を計算し、再起的に計算していく
  • これをfoldlを使って書くと以下のようになる
sum = foldl (+) 0
  • sum関数の場合はfoldlを使ってもfoldrを使っても同じように書けることになるがこれは加算演算子が結合順位で結果が変わらないから
  • foldlの定義は以下のようになる
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs
  • 例えば、foldrとfoldlで以下のような関数だと結果が異なってくる
divideList :: (Fractional a) => [a] -> a
divideList = foldr (/) 1

divideListL :: (Fractional a) => [a] -> a
divideListL = foldl (/) 1

main = do
    print $ divideList [1,2,3] -- 1.5
    print $ divideListL [1,2,3] -- 0.16666666666666666
  • 上記の例だとdivideListの場合1 / (2 / (3 / 1))となるがdivideListLの場合左結合で((1/2)/3となるため
  • foldrもfoldlもどっちも使える場合は計算的にどちらが効率が良いかなど考えた上で決める必要がある

関数合成

  • プレリュードで提供される(.)は二つの関数を合成した関数を返す高階演算子
  • この演算子の定義は以下のように定義できる
(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)
  • 上記の定義はラムダ式を使わずに明示的に引数xを書いても定義できるが、ラムダ式で書いたほうが関数が戻り値であることが明確
  • 関数合成は以下のように適用するとかっこが減り、引数が省略できるので簡潔に書ける
sumsqreven :: Integral a => [a] -> a
-- sumsqreven ns = sum (map (^2) (filter even ns))
sumsqreven = sum . map (^2) . filter even
  • 上記の関数合成の例を見るとわかるが関数合成は結合順位が結果に影響を与えないため、結合順位を示すかっこは不要
  • 関数合成を用いて関数を定義するスタイルをポイントフリースタイルという
  • ポイントとは値のことでつまり引数を用いない形式ということ
  • 関数合成には単位元のような役割を果たす関数idがある
id :: a -> a
id = \x -> x
  • これは引数をそのまま返す恒等関数である
  • これが必要となる場面はまだあまりイメージできないが例えば、以下のような関数合成の際の初期値として利用することができる
compose :: [a -> a] -> (a -> a)
compose = foldr (.) id
ぱんだぱんだ

型と型クラスの定義

  • Haskellにおいて新しい型を定義する1番簡単な方法は以下
type Bit = Int
  • これは既存の方の別名定義
  • String型はtype String = [Char]と定義されているように、[Char]の別名にすぎない
  • 型の別名定義は以下のように型変数を使って定義することもできる
type Pair a = (a, a)

type Assoc k v = [(k, v)]
  • 既存の型の別名ではなく完全に新しい型を宣言するにはdataを使う
  • 例えばプレリュードにあるBool型は以下のように宣言されている
data Bool = False | True
  • 上記のBoolの例でいうFalseとTrueのような型の値を構成子とよぶ
  • 構成子はHaskellにおいて何か意味があるものではない
  • dataにより新しく定義した型は以下のように構成子をパターンマッチングすることで意味をなしたりする
data Move = North | South | East | West
type Pos = (Int, Int)

move :: Move -> Pos -> Pos
move North (x, y) = (x, y+1)
move South (x,y) = (x,y-1)
move East (x,y) = (x+1,y)
move West (x,y) = (x-1,y)
  • 構成子は以下のように引数を取ることもできる
data Shape = Circle Float | Rect Float Float

square :: Float -> Shape
square n = Rect n n

area :: Shape -> Float
area (Circle r) = pi * r ^ 2
area (Rect x y) = x * y
  • CircleとRectは引数を取ることから関数であり、構成子関数と言える
  • 普通の関数と構成子関数の違いは構成子関数は定義に等式を持たず、純粋にデータを作るために存在しているというところ
  • Circle 1.0はこれ以上評価することはできない、Circle 1.0というデータでしかないということ
  • dataによる型宣言でも以下のように型変数を使用することができる
data Maybe a = Nothing | Just a
  • 構成子も引数も一つだけであれば以下のようにnewtypeを使って型定義することもできる
newtype Nat = N Int
  • 詳細はあんまり理解できていないがdataによる型宣言をするよりもnewtypeで宣言をしたほうが効率が良くなるらしい。
  • dataやnewtypeを用いて宣言される型は再帰的にも宣言できる
data Nat = Zero | Succ Nat
  • ちょっと型の再帰的な宣言は理解するのが難しかったのであんまり深掘りはしてない
  • 型クラスに関しては以下のように定義することができる
clas Eq a where
    (==), (/=) :: a -> a -> Bool
    x /= y = not (x == y)
  • 上記の例はプレリュードで定義されているEqクラスの宣言で型クラスEqのインスタンスになるには==と/=を実装している必要があるが、/=はデフォルト実装として実装されているので実際は==だけ実装すればいい
  • Eqクラスを実装するには以下のようにする
instance Eq Bool where
    False == False = True
    True == True = True
    _ == _ = False
  • これはパターンマッチを使ってEqクラスを実装している
  • ある型クラスを拡張したい場合は以下のようにしてある型クラスを拡張して新しい型クラスを定義することもできる
class Eq a => Ord a where
    (<), (<=), (>), (>=) :: a -> a -> Bool
    min, max :: a -> a -> a

    min x y | x <= y = x
                | otherwise = y
    max x y | x <= y = y
                | otherwise = x
  • 上記の例はプレリュードにあるOrdクラスの定義でEqクラスの実装に加え、6種類のメソッドを実装する必要があることを定義している
  • minとmaxはデフォルト実装になっているので実際は4種類の比較演算子を定義すればよい
  • 新しく宣言した型にEqやShowといった組み込みの型クラスのインスタンスとしたい場合はderivingという機能を使って自動的に実装することができる
ぱんだぱんだ

関手(ファンクター)

  • 以下の関数をとりあえず見てみる
inc :: [Int] -> [Int]
inc [] = []
inc (n:ns) = n+1 : inc ns

sqr :: [Int] -> [Int]
sqr [] = []
sqr (n:ns) = n^2 : sqr ns
  • 上記の例はリストの要素に適用している処理以外は同じなため抽象化できる
  • これを抽象化したものがリストにおけるmapである
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

inc = map (+1)
sqr = map (^2)
  • これはリストに限った話ではなく型変数を持つ多くの型にも当てはまります
  • このようなmap関数を提供するクラスを関手(ファンクター)と呼び、Haskellのプレリュードでは以下のように定義されている
class Functor f where
    fmap :: (a -> b) -> f a -> f b
  • リストにおけるfmapはmapそのものですし、Maybe型や型変数を持つ独自の型定義でもfmapを実装することができる
  • これらの例は関手fにおいてf a は型aの要素を持つデータ構造であるということからコンテナ型と呼ばれ、与えられた関数をそれぞれの要素に適用する
  • ただ、全てのファンクターがこの様式に従うわけではなく、例えばIO型がそうである
  • IO型は入出力のアクションを表し、内部構造を公開しないため、感覚的にはコンテナ型ではない
  • しかし、IO型はfmapを実装しファンクターになることはできる
  • 以下はIO型のfmapの実装
instance Functor IO where
    -- fmap :: (a -> b) -> IO a -> IO b
    fmap g mx = do { x <- mx; return (g x) }
  • 関手を使う主な利点は以下の2つ
    • 関手なら何でも、要素を処理するために関数fmapを利用することができるため、本質的に同じ複数の関数に対して、インスタンスごとに別の名前の関数を考えなくて良い
    • どんな関手にでも使える汎用的な関数を定義することができる。以下に関手の要素をプラス1する汎用的な関数の例
inc :: Functor f => f Int -> f Int
inc = fmap (+1)

inc (Just 1)
> Just 2

inc [1,2,3]
> [2,3,4]
  • 関手には関手になるためにfmapを実装すること以外に関手則を満たす必要がある
  • 関手則の説明に関しては省略
ぱんだぱんだ

アプリカティブ

  • 関手はある構造の中のそれぞれの要素に関数を適用するということの抽象化
  • 関手におけるmap関数の引数は一つだが、これを複数の引数に拡張した抽象化がアプリカティブ
  • Haskellのアプリカティブは以下のように定義されている
class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) ::f (a -> b) -> f a -> f b
  • 上記の定義にある2つの関数があればカリー化を利用して複数引数に対応できる
  • pureは型aの値を型f aの構造の中に入れる
  • <*>は関数適用($)の一般化
  • <*>の引数である関数と値、返り値全て構造fの中に格納される
  • 演算子の使い方は以下のような感じ
g <*> x <*> y <*> z
  • 演算子は左結合
  • gはカリー化された関数であるため、複数引数に対応できる
  • 以下は引数が3つの関数を使ったfmapの実装例
fmap3 :: (a -> b -> c -> d) -> f a -> f b -> f c -> f d
fmap3 g x y z = pure g <*> x <*> y <*> z
  • Maybeは関手であり、fmapが提供されているためアプリカティブにするのは簡単
instance Applicative Maybe where
    -- pure :: a -> Maybe a
    pure = Just
    -- <*> :: Maybe (a -> b) -> Maybe a -> Maybe b
    Nothing <*> _ = Nothing
    (Just g) <*> mx = fmap g mx
  • 上記のMaybeのアプリカティブはまずpure関数はa型の値を成功を表す値に変換する
  • <*>は失敗するかもしれない関数に失敗するかもしれない引数を与え、失敗するかもしれない結果を返す
  • このMaybeのアプリカティブスタイルの何が嬉しいかというと純粋な関数を失敗するかもしれない引数に適用し、例外を伴うプログラミングを提供してくれるということ
  • つまり、例外(副作用のある)プログラムを純粋関数として扱えるということ
  • 次にリストにおけるアプリカティブを考えてみる
instance Applicative [] where
    -- pure :: a -> [a]
   pure x = [x]
    -- (<*>) :: [a -> b] -> [a] -> [b]
   gs <*> xs = [g x | g <- gs, x <- xs]
  • pure関数はa型の値をリスト内に格納し、要素数1のリストとする
  • <*>は関数のリストと値のリストを引数にとり、それぞれの関数をそれぞれの引数のリストの要素に適用し、全ての結果を一つのリストに格納して返すことができる
  • 以下は2つの整数のリストに対して全ての掛け算の結果を返す関数の例
prods :: [Int] -> [Int] -> [Int]
prods xs ys = [x * y | x <- xs, y <- ys]

-- アプリカティブスタイル
prods xs ys = pure (*) <*> xs <*> ys
  • 使用例は以下
main = do
  print $ prods [1, 2, 3] [10, 100, 1000]

-- [10,100,1000,20,200,2000,30,300,3000]
  • この例から何が言えるかというとリストをアプリカティブスタイルで使うことで非決定性プログラミングの枠組みが提供されるということ
  • 引数の選択だったり失敗の伝達はアプリカティブがいい感じに処理してくれるので考えなくて良く、複数の純粋な関数を複数の引数に適用できる
  • 次にIO型のアプリかティブの使用をみていく
  • IO型のアプリカティブは以下のように定義できる
instance Applicative IO where
    -- pure :: a -> IO a
    pure = return
    -- (<*>) :: IO (a -> b) -> IO a -> IO b
    mg <*> mx = do {g <- mg; x <- mx; return (g x)}
  • アプリカティブを使うことで副作用を持つ関数を副作用のある引数に適用し、副作用のある結果を返すことかできる
  • 以下はIO型のアプリカティブの例で、指定された回数だけキーボードからの入力を読み込む関数
getChars :: Int -> IO String
getChars 0 = return []
getChars n = pure (:) <*> getChar <*> getChars (n - 1)
  • 上記の例からわかる通り純粋な関数を副作用のある引数に適用することができるようになる
ぱんだぱんだ

モナド

  • とりあえず以下のような関数を考えてみる
data Expr = Val Int | Div Expr Expr

eval :: Expr -> Int
eval (Val n) = n
eval (Div x y) = eval x `div` eval y
  • これは除算を表した関数定義で使う場合は以下のようになる
print $ eval (Div (Val 10) (Val 5))
> 2
  • ただし、これは0除算するとエラーになってしまうので以下のようにMaybeを使って安全に除算することができる
safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv x y = Just (x `div` y)

eval' :: Expr -> Maybe Int
eval' (Val n) = Just n
eval' (Div x y) = case eval' x of
  Nothing -> Nothing
  Just n -> case eval' y of
    Nothing -> Nothing
    Just m -> safediv n m
  • これで安全に除算することができるようになったが処理が冗長
  • そこでMaybeは前回学んだアプリカティブになることができるため以下のように書いてみる
eval'' :: Expr -> Maybe Int
eval'' (Val n) = pure n
eval'' (Div x y) = pure safediv <*> eval'' x <*> eval'' y
  • これはうまくいかない
  • なぜなら、pure safedivの部分がMaybe (Int -> Int -> Int)を期待するのに、実際はMaybe (Int -> Int Maybe Int)となるため型が合わないから
  • つまり、アプリカティブでは純粋な関数を扱うことを想定していて、失敗するかもしれない関数を適用することができないということ
  • そこでモナドが登場する
  • 先にいうとモナドとはbind演算子を実装し、モナド則を満たしたアプリカティブのことである
  • eval :: Expr -> Maybe Intを簡潔に定義するにはMaybeについて場合分けする部分を抽象化すると良さそうで、実際に抽象化してみると以下のようなbind演算子が定義できる
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
mx >>= f = case mx of
    Nothing -> Nothing
    Just x -> f x
  • このbind演算子を適用してラムダ式を使ってevalを定義し直すと以下のようにかける
eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = eval x >>= \n ->
                          eval y >>= \m ->
                          safediv n m
  • Haskellでは以下のようなシュガーシンタックスが用意されており、それがdo構文である
eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = do n <- eval x
                               m <- eval y
                                safediv n m
  • これがモナドと呼ばれるものでMaybe型は関手にもなれるしアプリカティブにもなれるしモナドにもなれるが、ListやIOも同じようにモナドになれるため、do表記が使える
  • モナドは組み込みで以下のように定義されている
class Applicative m => Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

    return = pure
ぱんだぱんだ

Traversable

  • 関手が実装しているfmapで関数をデータ構造の中に適用できることを学んだが失敗するかもしれない関数a -> Maybe bのような関数でfmapしたいときHaskellではTraversableという一般化されたクラスが用意されている
  • 一応、一読した程度で上記のような理解で留めておく
ぱんだぱんだ

遅延評価

  • 関数の適用についてのはなし
inc :: Int -> Int
inc n = n + 1
  • 上記のような関数があってinc (2*3)を実行するとき、2*3を先に評価するのかincを先に評価するのか評価戦略がこの簡単な関数でも複数あることがわかる
  • Haskellにおいてこの評価戦略は停止するのであればどちらを選んでも同じ結果を算出するという重要な性質がある
  • 一般的な命令形の言語では変数の値を変えることが計算方法の基本でありこのような性質はない
  • 一つ以上の引数へ適用されている関数が含まれていて、その適用を実行することで簡約が可能な式を簡約可能式と呼ぶ
  • 以下に簡単な例を
mult :: (Int, Int) -> Int
mult (x,y) = x*y

-- 15
mult (1+2, 2+3)
  • 上記の例では簡約可能式が３つある
  • 1+2と2+3と式全体である
  • どういう順番で簡約すべきかについて最内簡約と最外簡約の２つがある
  • この簡約の仕方で関数適用における値渡しと名前渡しが決まり、最内簡約が値渡しとなり最外簡約が名前渡しとなる
  • この簡約の方法はこれから説明する停止性と遅延評価に大きく関係してくるため重要な考えである
  • 先に停止性について
  • 例えば、以下のような値を評価しようとすると無限ループになりプログラムは停止しない
inf :: Int
inf = 1 + inf
  • では以下の例はどうだろうか
fst (0, inf)
  • fstはタプルの最初の要素を取り出すプレリュード関数だが、infが値渡しで評価される場合、無限ループになりプログラムは停止しない
  • しかし、名前渡しの場合infは評価されず正常にプログラムは停止する
  • このように、名前渡しには式の評価を必ず停止させ、同じ結果を返すという重要な性質がある
  • つまり、評価をなるべく多く停止させたいなら値渡しよりも名前渡しのほうが適しているといえる
  • しかし、名前渡しを採用する場合、式の評価が後回しになっていくので簡約の回数が増えることになる
  • これは式の評価回数が増えるため効率が悪くなる可能性があるが、これはポインターを利用することで回避することができる
  • ポインターによる共有を用いた名前渡しは遅延評価と呼ばれ、Haskellではこれが採用されている
  • そのため、Haskellは遅延プログラミング言語と呼ばれたりする
このスクラップは2日前にクローズされました