入門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
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
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)
...

型と演算

read :: Read a => String -> a

  • どの型に変換するか、はコンパイラ型推論により(その後の値の使われ方を見て)判断してくれる
  • $はMonadで勉強する

遅延評価

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")