入門Haskell
Haskellの参考本をしっかりと読んでみた。
Monadはまだまだ理解が追いついていないので、並列プログラミング(Par monad/Eval monad)はもう少し後にしよう。以下、ざっくりメモ。
基本
- 関数も変数も区別しない
関数は透過参照性がある(同じ引数であれば常に同じ値を返す)
副作用のある処理(IOなど)はdo式で実行する
- do式は式の実行順序を定義する
- StringとIO Stringは異なる型
- 関数は透過参照性があるので通常はIO Stringは受け取れない
do式はIO StringをStringに変換してくれる(do式で書いた関数はIO Stringを受け取れる)
配列(インデックスアクセスによるO(1)での参照)は無い
- リストは連結リスト(O(n)での参照)
型付け有無 | 型推論 | 型付け性質 | 型安全 | |
---|---|---|---|---|
C言語 | 静的型付け | 型推論なし(intになる) | 弱い型付け(条件に数値を取ることができる) | 型安全でない |
Haskell | 静的型付け | 型推論あり | 強い型付け(型によって除算の演算子が違う) | 型安全 |
Ocaml | 静的型付け | 型推論あり | 非常に強い型付け(型によって演算子が違う) | 型安全 |
Ruby | 動的型付け | 型推論あり | 弱い型付け | 型安全でない |
カリー化
- sum関数はfoldlをカリー化したもの
foldl :: (a->b->a)->a->[b]->a sum = foldl (\x y->x+y) 0 sum = foldl(+) 0 Prelude> :t (+) (+) :: Num a => a -> a -> a
セクションは2項演算子のカリー化
- (+)に部分適用すると(+10)とか(100+)とか書ける
- (/2)とか(10/)とか
- 減算には注意((-)1)
!=ではなく/=
型クラス
Prelude> :t (==) (==) :: Eq a => a -> a -> Bool
- Eq a => は、aが型クラスEqのインスタンスであることを明示
Prelude> :info Eq class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool -- Defined in `GHC.Classes' instance Eq a => Eq (Maybe a) -- Defined in `Data.Maybe' instance (Eq a, Eq b) => Eq (Either a b) -- Defined in `Data.Either' …
- 順序の定まる型クラスOrd (Orderable)
- class Eq a => Ord a where
- Eqをスーパークラスに持つ
Prelude> :info Ord class Eq a => Ord a where compare :: a -> a -> Ordering (<) :: a -> a -> Bool (>=) :: a -> a -> Bool (>) :: a -> a -> Bool (<=) :: a -> a -> Bool max :: a -> a -> a min :: a -> a -> a -- Defined in `GHC.Classes' instance Ord a => Ord (Maybe a) -- Defined in `Data.Maybe' instance (Ord a, Ord b) => Ord (Either a b) ...
型と演算
- / は浮動小数点(Fractional型)
`div` は整数(Integral型)
Note : 多倍長整数
- 処理系に依存しない桁の整数表現が可能
- http://idm.s9.xrea.com/factorization/multiprec/multiprec.html
- 各桁をその処理系の最大桁数のn進数で表し、各桁を要素とする配列で表現する(rubyやJavaの多倍長整数は処理が遅いので注意)
read :: Read a => String -> a
遅延評価
fib = 0:1:(zipWith (+) fib (tail fib))
- まず2つの要素があれば、
zipWith f a (tail a)
は計算できる - 1つめと2つめの要素を使って、3つめの要素が決まる
- すると、2つめと3つめの要素を使って、4つめの要素が決まる
- 次の要素が必要になった場合に計算する
自分自身を使う場合、必ず先頭の要素が必要になる(でないと、次の要素が計算できない)
Note : data は代数的データ型(特定の数の代わりとして用いられる文字・記号などのこと)
Maybe
data Maybe a = Nothing | Just a
- MaybeはNothingかJust aを持つ
- Just aはそのままではaとして使えないので取り出す必要がある
data Bool = True | False
これもTrueとかFalseに意味はなく区別しているだけ
Maybeは型構成子
Justはデータ構成子
関数の値をMaybe型にしておくとことで、必然的にエラーチェックを行うことになる
- どのような場合にNothingを返すのか、定義しないとコンパイルエラーになるため(一方Cでは、NULLを返すケースを書かなければならない、という定義ができない)
Monad
- 副作用のある処理は順序が重要になってくる
- 一方で、Haskellの関数は参照透明であり、実行する順序にはこだわらない(引数が同じであれば、どの順序で実行しようとも同じ結果になる)
- do記法は>>=の糖衣構文で、上から順に(あるいは;で区切られた順で)実行する
- return はラベルをつけてMonadとして返す
putStr “Hoge”
= return “Hoge” >>= putStr
- StringをIO StringというMonadとして変換し、putStrに入力して実行する
words, lines関数
import System.Environment import Data.Char wordsCount f [] = 0 wordsCount f (c:cs) | isAlphaNum c = f (inWords cs) | c == '`' = inQuote cs | otherwise = outWords cs where inWords cs = wordsCount id cs outWords cs = wordsCount (\n->1+n) cs inQuote [] = 0 inQuote (c:cs) = case c of '\'' -> 1 + wordsCount (\n->1+n) cs _ -> inQuote cs wordsCountMain str = putStr(show(wordsCount (\n->1+n) str)) outLines [] = 0 outLines (c:cs) | c == '\n' = outLines cs | otherwise = 1 + inLines cs inLines [] = 0 inLines (c:cs) | c == '\n' = outLines cs | otherwise = inLines cs linesCountMain str = putStr(show(outLines str)) countMain arg = do wordsCountMain arg putStr(" ") linesCountMain arg putStrLn("") main = do args <- getArgs mapM_ countMain args putStrLn("Finished")