先にまとめ

Haskellに超入門した
Haskell、結構思考にマッチしやすくていいなー
- でもアクションとか入ってくると、必ずしもそうばっかりじゃなさそう、というかそっちが本気モードっぽい
説明があいまいさを残さないように話しててよかった
結構なペースだったけどこのくらいの勢いでやるほうが気合入っていいな
続きもやりたかったけど来週は予定が合わなくてぐぬぬ。。。自習しよう＞＜

Haskel超入門

この会の趣旨
- 明日の機械語入門の中で必要なHaskellの文法を学ぶのが元々の主旨
- Halkellの難しい内容をやるわけではない
  - ラムダ・モナドは出さない
- なれることが目的

Haskelで最低限必要な文法

重要なキーワードは「再帰」

Hello World

module Main whereはなくても動く
Main.hsのファイル名とmoduleの名前は一緒じゃないとダメ。
main =の部分はCでいうmain関数みたいなものと考えておく(アクションという)
--は行コメント。複数行コメントは{- -}でかく
do は今は説明しない。

束縛

Haskellでは変数に再代入、という事ができない
結び付きが強い。なので束縛という。代入とは言わない

変数

トップレベル変数
- いわゆるグローバル変数
- c = a + bに書けばいい
ローカル変数
- where
  - 最初に変数の処理を書いといて、あとから変数を定義する
  - 普通と順番が逆
- let
  - 普通の言語と同じく、先に定義する
  - doのあるなしで、文法が変わる
- 今回は、letがめんどくさいのでwhere使う

関数

数学の関数のカッコのない版
- =のあとの式の答えがそのまま返り値
halskellにCのreturnに相当するものはない。違う意味のreturnはない
関数の返り値をprintするときはprint(f 1)と書くことができる
毎回カッコが面倒な場合はprint $ f 1のようにかける。
- $と書けば、それ移行の部分はカッコに囲われているように

関数の演算子化

2津の引数を取る関数をバッククォートで囲むと、中置演算子として引数の間に関数を置ける
- あとで割り算とかで使ったりする

演算子の関数化

さっきの逆
- 中置演算子をカッコでかこうと、関数のように前における

四則演算子

除算は/でわると、整数同士の演算でも小数点で帰ってくる
- 代わりにdiv, modがある

命名規則

変数と関数は小文字から始めないとダメ
- 大文字ではじめるとエラー

条件分岐

if then else
- 等しい、は==, not equalは/=。他の言語と違うので注意
複数行に分ける場合は、then,elseをインデントしてifに従属してることを明示する必要がある
- ちなみに、doがついてない場合は、インデントなくてもよくなる(あってもよい)
- ここでは、あってもなくても使える話を紹介
if自体が値を返せる
- pritn $ if a == 1 then "1" else "?"のように書ける
- 三項演算子のように使える
- あんまり出てこない

パターンマッチ

Haskellらしい書き方
関数内でifで切り分ける代わりに、特定の引数の場合に関数を分割定義できる
これをパターンマッチという
- ちなみに。どこでも使わない引数は_で定義する
  - 引数を無視していることの明示

階乗

再帰の例としてよく出される
関数定義の中で自分を呼んでる
再帰は往復である
- fact 1がストッパーとなり、反転して復路に入る
再帰の実装をミスるとよく無限ループになる
文法にループがないので、繰り返しは再帰で書く！

再帰のコツ

複雑なプログラムになってくると、いちいちステップ考えられない
再帰の流れは、結果が信頼できるとみなして考えると、理解しやすい
- これはこう定義したんだから、こう動くはず！というのでまずテストしてみる
数学的帰納法的な発想で考えると、効率よい
- 再帰の発想と、やってることが基本的に同じ

ガード

くせのある書き方
要するにif。|を使う
関数定義の際に使う
Haskellだと、なるべくifは書かずにパターンマッチとガードで書く、という作法

ガードとパターンマッチの使い分け

まずパターンマッチでかけないかを考える
範囲指定などが必要で、パターンマッチが使えない場合はガードを使う
- パターンマッチでおおまかに分けたあと、ガードで細かく振り分ける場合もある

case - of

関数の中でパターンマッチを使う
- =ではなく->をつかう
- トップレベルの場合わけではないぞ、ということを明示するために別の記号になってる

練習

フィボナッチ数と作ってみる
- パターンマッチで書く
- ガードで書く
- case - ofでかく

リストの先頭に挿入
print $ 1:[2..5]
- この後山のように出てくる
応用
print $ 1:2:[3..5]のように書ける
末尾への追加はできないので、[1..4] ++ [5]とかく
- コロンは対称な演算子ではない
リストa = [1..4]はそもそも1 -> 2 -> 3 -> 4 -> end という構造してる
- なので、b = 2:aみたいなことをしても、aに影響を与えない
- だから、前に値をつけることは可能
- 後ろにつけようとすると、aの構造に影響を与えてしまうからダメ
- ++の場合は、前の配列とも後ろの配列とも違う新しい配列を作ってくっつけるのでOK
- 当然、その処理の差のため、:の方が処理速度が早い。++はちょっと遅い

文字列

文字列は、文字のリスト
- "abcde"と['a', 'b', 'c', 'd', 'e']と['a'..'e']は内部的に同じ
Haskellは文字と文字列は区別あり
- ""は文字列、''は文字
- Cと同じ
||使って一文字取り出すこともできる
リストに対する操作と同じことを考えればいい

引数

引数でリストの先頭要素を取り出せる
(x:xs)みたいにかける
- 慣習として複数のものに複数形の変数(xs)をつける
- 長い変数を嫌う文化。記号的な変数を使う習慣がある
- 使ってないなら(x:_)とか書くと良い
複数の分割にも使える
- f (_:x:_) = x で2番目だけ取れる
- 先頭いくつ、というのを想定した引数の場合は、その数が満たない場合はエラーになる

リスト関係の関数

length
- リストの要素数
take
- 先頭からn個を取る
drop
- takeの逆。先頭のnこを落とす
reverse
- リストを逆順にする
sum
- リストの和
product
- リストの積

練習

関数名に'(ダッシュ)を利用できるよ
紹介した関数を再実装してみる

タプル

複数の値をかっこで囲んだ部分のこと。値同士はカンマで区切る
関数から複数の値を帰す場合などに使う
リストと似てる
- リスト = 可変長, 全て同じ型
- タプル = 固定長, 異なる型を混ぜられる
受け取るとき、分割し受け取ることも可能
- (a1, a2) = addsub 1 2
数学の座標をイメージするとわかりやすい

タプル用の関数

fst
- タプルの1番目を取り出す
snd
- タプルの2番目を取り出す
ただし、これらは要素が2つのタプルにしか使えない
要素3つ以上の場合は分割して変数経由で値を取り出します
- (_, _, p3z) = p3
- !!などで取り出すこともできない。リストとは別物

練習

数学！
タプルを座標に見立てる

import

ライブラリを読み込む
読み込む名前空間を指定して、ライブラリを読む

練習

ROT13というシーザー暗号を実装してみる

ソート

挿入ソートの実装の流れを追って見る
insertの第2引数は、「必ずsortが済んだものが来る」という前提で組んでいく
では、insertをどうやっているか
- 前から順に比較していって、ちょうどいいところに来たらそこに収める
キモは、「常に第2引数がソート済みだ」とかんがえるところ
- そういう関数だから。それを再帰的に呼んでいるから
- 再帰の結果を信頼する！
  - 1段階の定義をしっかりしておけば、あとはきちんと行く

デバッグ

普通にprintfデバッグしたいよ、という話
Debug.Trace.trace を使うとできる
traceは、標準エラー出力に出す
- 標準出力と混ざるとややこしいので、traceIOを使う
- showを使うと、数値などを文字列にすることができる

練習

バブルソートとマージソート実装

バブルソート

値を2つずつ比較していってソートする
- 右端から比較していくと、1周すれば、かならず左端が必ず最小になる
- それが終わったら、終わった左端を除いて再び同じことをする
- これを繰り返すと、どんどん減っていってソートが完了する
何故バブルソートというのか？
- 縦の図にするとわかる
- 小さいものが上の方に移動していくイメージになる
- 水の中の泡が水面に向かって浮かんでいってるイメージ
  - 軽いものが上に浮かぶ、なのでバブルソート
2つの関数に分けて実装すると、よさ気
逆に、大 > 小の順になるようにするほうが楽
バブルソート自体は計算量があまり良くないので、実務じゃ使わないようにね

マージソート

もっとマシなソート
とりあえずバラして、くっつけるときにソートする

リスト内包表記

数学でよくあるやつ
リストの中になんか式っぽいものを書いてる
リストがあって、それに対して全部に同じ操作をする手法
- mapでも同じことができる

条件指定

リスト内包表記で適用する場合に、要素を取り出す際に条件をつけることができる
- filterでも同じことができる

練習

クイックソート
- コードは提示するのでtraceしたりしながら理解を試みる
- 手軽なんだけど、並び順に依存する
- 計算量がそれに依存する
  - 安定ソートじゃない
- そのため、マージソートの方が好まれてる
説明してみる
- 配列の先頭から要素nを取り出して、他の要素と比較する
- 配列の残りの要素を、nより大きい配列gteqとnより小さい配列ltに分ける
- nは、これらの配列の間に配置する
- 更に、それらの配列lt, gteqに対して上記の操作を再帰的に実施する
- 全て結合すると、sortされる

内包表記の組み合わせ

複数のリストから要素を取り出すことができる
- 多重ループになる
- 総当りに使える

練習

直角三角形 -> 三平方使う

Haskelアクション超入門

超入門は計算だけ、みたいな感じになっちゃってたけど、もっと実用的に
doとはなにか、という部分の実用的な話
- モナドや圏論などには触れない。

参照透過性

同じ引数に対しては、常に同じ値を返す性質
- 関数に同じ引数を与えたら、常に同じ結果になる
入力に対して、出力が1対1になる

副作用

Haskellでは、参照透過性のない関数は定義できない
- 乱数のような、毎回異なる結果になるもの
毎回結果が異なる = 内部に状態を持っている
- そのような状態が変化することを副作用という
- 参照透過性と対立する概念
副作用がある = 参照透過性がない
- 現在時刻の呼び出し、などは参照透過性がない
- そういうのもひっくるめて副作用がある
では、そういうものをHaskellではどうやって扱うか？

アクション

副作用が扱えないと困ることがある
関数は無理だが、関数の「ようなもの」が定義できる
それがアクション
関数とは呼び出し方が違う
- 見た目自体違う

乱数

アクションのサンプル
dependeicesを追加しないとできないよ

`<-`

アクションから値を取り出すのに使う
<-は、doの中でしか使えない
アクションを使うためには、doブロックの中でしか使えないという状態
doをつけると、モードが切り替わると思っとくといい
- doのない世界は、参照透過な世界
- 参照透過性を何とかしないといけないので、そういうモードを用意した、みたいな感じ。。。

letとの関係

let自体は成功するが、printの段階でエラーになる
letでアクションにつかっても、アクション自体と同じモノを指す
- アクションに対して別の名前をつけている状態
アクションから値を取り出すには、<-を使うしか無い

bind

一時変数を経由せずにアクションから直接値を取り出そうとしてもダメ
print randAlphaとかはエラー
それを何とかするための演算子がある

`=<<`

bindと呼ぶ記号
これを使うことで、直接アクションから値を取り出して、他の関数などに渡せる
- 無理して使うと気持ち悪いので、なれないうちは一時変数を使うといい
iostreamの<<の値を流し込むイメージを持っておくといい
- 等しいわけじゃないよ

`>>=`

逆向きもある
というか、本来のbindは、こっち向き
- 説明の流れで逆から話した
dice >>= print
厳密には、bindはアクションと、アクションを返す関数を結びつけている
- どんな関数でもいい、という話ではない
- アクションを返さない関数に渡すとエラーになる
- この辺を理解するためにはモナドを理解する必要がある
一時変数を経由すると、その時点でただの値になるので、そういった制約はなくなる
ちなみに、<-の実体も本当はbindだけど、ラムダ式とかを理解してから学ぶほうがいい

IO

今回扱うアクションは、全てIOと呼ばれる型
- IO+型と表記される
  - 多相型
  - ジェネリクスみたいなもの
厳密に言うとIOアクションと呼ばなければいけない
具体例
- IO Char -> 文字が取り出せるアクション
- IO Charでひとつの型を表す
- IOがアクションを、Charが取り出される型を表す

型注釈

型を明示する行
一般的には本体の上に書く
- なくても、型推論があるので多くの場合は動く
- 型推論しきれない場合、エラーになって、その旨のエラーが出る

Unit

空のタプル() = 値がないことを示す。
これをUnitと呼ぶ
- voidとかに相当するもの
返り値なし、というものの代用

print

実は、printは()を返すアクション
アクションだということは、値を取り出す操作をしなければ、文字は表示されない
doの中のセンテンスは実は一つ一つのアクションから値を取り出し、それを捨てるという操作をしている
- doの中に書いたアクションは自動で値を引っこ抜かれる
- なので、アクションを返さない関数をベタ書きするとエラーになる
イメージとしては、「値を引っこ抜かれた時に、副作用として何か動作をする」という感じ

アクションを返す関数

print自体はアクションではなく、アクションを返す関数

do

doの中は、全部bindでつながっている
一度IOアクションを使ってしまうと、中では全部IOじゃないと。。。みたいな感染性がある
do の中は、そこから下自体がまるごとアクションになっている

戻り値

doブロックはアクションを返す必要がある
最後に書いたアクションが、doブロック自体の戻り値になる
- なので、最後の行にアクションじゃないものを書くと、エラーになる

return

<-の逆で、アクションに値をいれて返す関数
- 引っこ抜くとただ入れた値が帰ってくるだけ。副作用が特にない
なお、普通の言語ではreturnて書くと関数から抜けるが、Haskellのreturnは抜ける機能はない
- Cの見た目を真似てるだけ
なので、途中にreturnを書いても素通りと変わらない
- 書いても意味ない

main

doブロック全体が、ひとつの変数に束縛されてる状態
mainも同じ状態
mainから値を取り出すのは誰がやるのか？
- それ自体はプログラムの起動時にHaskellさんが勝手にやる
最初に、doを省略してprint書いても1行だけ動くよ、という話をしたのは、printもアクションを返すからうまいこと動くだけ

bindの結合先

アクションを返さない関数にはbindできない
- サンプルの中からreturnを取り除いたりすると、エラーになる
なぜそうなの？
- 一度アクション = 副作用に手を付けたら、二度と副作用のないきれいな世界に返さないようにするため
- そのように、アクションが感染していく
- 参照透過性を保つため

複数の引数

カッコを使うと、bindで複数の引数をわたせる
- 厳密に言うと、カリー化してる

Applicativeスタイル

<$>
- 普通の関数に対してアクションを渡して、その戻り値をアクションに閉じ込める
<*>
- 複数の引数を渡すときに、これでつなぐ
結局返り値はアクションになるので、縛りから抜けられるわけじゃない

デバッグ

traceは実は、副作用を隠してるインチキ関数
これをputStrLnで書きなおすとどうなるか？
- ちなみにprintを使うと""が出てきちゃってうっとおしいのでこっち使ってみた
一回IOにまみれたものを使っちゃうと、その関数自体をアクションになっちゃってとても面倒になる

IORef

アクションを使うと、値が変更できる変数みたいなものが実現できる
今日はここまで...

練習で書いたコード

ほぼ制限時間で出来たよかった！
シュレディンガーの猫だけできなくて正答の写し。
- まぁ教わってない範囲を使う必要あったから仕方ない。。。(-ω-。)

module Main where
import Data.Char
import Debug.Trace
import System.Random

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

fib2 n
    | n == 0    = 0
    | n == 1    = 1
    | otherwise = fib2 (n - 1) + fib2 (n - 2)

fib3 n = case n of
    0 -> 0
    1 -> 1
    _ -> fib3 (n - 1) + fib3 (n - 2)

length' [] = 0
length' (_:xs) = 1 + length' xs

take' _ [] = []
take' 0 _ = []
take' n (x:xs) = x:take' (n - 1) xs

drop' _ [] = []
drop' 0 xs = xs
drop' n (_:xs) = drop' (n - 1) xs

reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]

sum' [] = 0
sum' (x:xs) = x + sum' xs

product' [] = 1
product' (x:xs) = x * product' xs

fact n = product [1..n]

fact2 1 = 1
fact2 n = n * fact2 (n - 1)

perpPoint (p, q) (a, b, c) = ((a * c - a * b * q +  b * b * p)/(b * b + a * a),c - a * ((a * c - a * b * q +  b * b * p)/(b * b + a * a)))

rot13ch ch
    | ord ch > 78    = chr ((ord ch) + 13)
    | otherwise     = chr ((ord ch) - 13)
rot13 [] = []
rot13 (x:str) = rot13ch x:rot13 str


bsort'' (x:[]) = (x, [])
bsort'' (x:xs) = (s, (b:sorted))
    where
        (y, sorted) = bsort'' xs
        (s, b) = if x > y then (y, x) else (x, y)

bsort' [] = []
bsort' xs = x:bsort' xs'
    where
        (x, xs') = bsort'' xs

merge (xs, []) = xs
merge ([], ys) = ys
merge (x:xs, y:ys)
    | x < y     = x:merge (xs, y:ys)
    | otherwise = y:merge (x:xs, ys)

msort [] = []
msort (x:[]) = [x]
msort xs = merge (msort xs', msort xs'')
    where
        len     = length xs
        half    = len `div` 2
        xs'     = take half xs
        xs''    = drop half xs

qsort [] = []
qsort (n:xs) = qsort lt ++ [n] ++ qsort gteq
    where
        lt      = [x | x <- xs, x < n]
        gteq    = [x | x <- xs, x >= n]

qsortd [] = trace "[]" []
qsortd (n:xs) = trace dbg ret
    where
        ret = qsortd lt ++ [n] ++ qsortd gteq
        lt      = [x | x <- xs, x < n]
        gteq    = [x | x <- xs, x >= n]
        dbg = "(qsort low = " ++ show lt ++ "n = " ++ show n ++ " hight = " ++ show gteq ++ ")"

randAlpha = getStdRandom $ randomR ('A', 'Z')

rand :: IO Int
rand = getStdRandom $ randomR(0, 1)

box = do
    r <- rand
    return $ ["dead", "alive"] !! r

qsortdd [] = do
    return []
    
qsortdd (n:xs) = do
    let lt   = [x | x <- xs, x <  n]
    let gteq = [x | x <- xs, x >= n]
    let dbg = "qsort " ++ show (n:xs) ++ " = qsort " ++
               show lt ++ " ++ " ++ show [n] ++ " ++ " ++ show gteq
    low <- qsortdd lt
    great <- qsortdd gteq
    let ret = low ++ [n] ++ great
    putStrLn dbg
    return ret

main = do
    print "fib"
    print $ fib 5
    print $ fib2 6
    print $ fib3 7
    print "length"
    print $ length [1,2,3]
    print $ length' [1, 2, 3]
    print "take"
    print $ take 3 [1,2,3,4]
    print $ take' 3 [1,2,3,4]
    print "drop"
    print $ drop 2 [1,2,3,4]
    print $ drop' 2 [1,2,3,4]
    print "reverse"
    print $ reverse [1..4]
    print $ reverse' [1..4]
    print "sum"
    print $ sum [1..4]
    print $ sum' [1..4]
    print "product"
    print $ product [1..4]
    print $ product' [1..4]
    print "fact"
    print $ fact 5
    print $ fact2 5
    print "perpPoint"
    print $ perpPoint (0, 2) (1, -1, 0)
    print "ROT13"
    print $ rot13 "hello"
    print "bubble sort"
    print $ bsort'' [4,2,5,3,1]
    print $ bsort' [4,2,5,3,1]
    print $ bsort' [4,5,2,1,3]
    print "merge sort"
    print $ msort [4,5,2,1,3]
    print $ qsort [4, 6, 9, 8, 3, 5, 1, 7, 2]
    -- traceIO $ show $ qsortd [4, 6, 9, 8, 3, 5, 1, 7, 2]
    print $ [(x,y,z) | x <- [1..20], y <- [1..20], z <- [1..20], x * x + y * y == z * z]
    print $ [(x,y,z) 
            | x <- [1..20], y <- [1..20], z <- [1..20]
            , x * x + y * y == z * z
            , x < y
            ]
    print $ [(x,y,z) 
            | x <- [1..20], y <- [x..20], z <- [1..20]
            , x * x + y * y == z * z
            ]
    r <- randAlpha
    print r
    r <- randAlpha
    print r
    r <- randAlpha
    print r
    
    cat <- box
    print cat
    print =<< qsortdd [4, 6, 9, 8, 3, 5, 1, 7, 2]

先にまとめ

Haskel超入門

Haskelで最低限必要な文法

束縛

変数

関数

関数の演算子化

演算子の関数化

四則演算子

条件分岐

パターンマッチ

階乗

再帰のコツ

ガード

ガードとパターンマッチの使い分け

case - of

練習

リスト

!!

連番

++

:

文字列

引数

リスト関係の関数

練習

タプル

タプル用の関数

練習

import

練習

ソート

練習

リスト内包表記

条件指定

練習

内包表記の組み合わせ

練習

Haskelアクション超入門

参照透過性

副作用

アクション

乱数

<-

letとの関係

bind

=<<

>>=

IO

型注釈

Unit

print

アクションを返す関数

do

戻り値

return

main

bindの結合先

複数の引数

Applicativeスタイル

IORef

練習で書いたコード

`!!`

`++`

`:`

`<-`

`=<<`

`>>=`