第2回スタートHaskellに来ていますので、レポートします。といっても、中身は全てProgramming in Haskell の話なのですが。
宿題の解説 / @yuzutechnology さん
宿題の答え合わせ。
第5章 リスト内包表記 / @dekosuke さん
- 前回 矢印 Prelude と 型クラス、多相型、カリー化、ガード、パターンマッチ
- なぜリスト操作が必要なの？
- 関数型には一般的 にはforループがない
- forやwhileはリスト、Iterator はFunctor
- リスト内包表記は、リストからリストへの演算。
- 無名関数+map+filterでも書ける。ケースバイケース。
- [x^2 | x <- [1..5]] map の例
- [x | x <- [1..6], mod x 2 == 0] filter の例
- [(x, y) | x <- [1..3], y <- [x..3]] 複数の生成器を使う例
- リストを1つの値にまとめる関数(reduce(fold) など)とあわせて使うとよい
- length xs = sum [1 | _ <- xs]
- zip → 2つのリストを、1つのタプルのリストに
- 文字列の内包表記 → type String = [Char] なので
- シーザー暗号を作って解読
- encode n "..." はn文字ずらす
- shift n c は、小文字だけをn文字ずらす
- encode n xs = [shift n x | x <- xs]
- table として英文でのアルファベットの頻度表を用意
- 25パターンのズラす量を全てχ2乗検定にかけ、誤差がもっとも低い物を採用すれば、シーザー暗号は解ける
- Haskell で内包表記はあまり使わないのでは？ → プロジェクトオイラーとかでは使う。Pythonに比べるとあまり使わないイメージ
発表：第6章 再帰関数 / Lost_dogさん
- 再帰的定義 → 定義の中に自分自身が現れる
- 定義の中に自分自身が現れる関数を、再帰的関数と呼ぶ
- frac 0 = 1; frac n = n * frac (n-1)
- 再帰的関数の作り方
- 1. 型を作る : product :: [Int] -> Int
- 2. 基底部と再帰部を作る product [] = ??? ; product (n:ns) = ???
- 3. 楽な方を先に実装(だいたいは基底部) product [] = 1
- 4. 大変な方を実装。productはもう動く物と思って作る product (n:ns) = n * product ns
- 補足
- Q. for がよくないってのはどういう話？
- for のbreakやcontinue で型チェックはしてない
- for の中でも、変数の型のチェックがあるのでは？ → そこまで簡単だとそうだけど、複雑になると・・・
- 関数と文(for)を比較しているのが問題なのでは → 大事なのは、全てが"式"である、ということ
- for は構文であって副作用を期待しており、何を計算しているのかが不明確、ってことでは？
- OCaml とかでは、forの中にはinitを返す式しか書けなかったりもする
発表：再帰関数（補足） / トラビスさん
- factorial → 負の数を渡すと、無限ループ
- これは"部分関数"という。終了しないのは危険なので、error を使った方がいい
- n | n <= 0 = error "...negative"
- ケース文にて、頻度が高い物は上にした方がいい*1 → n > 0 を一番上
- Q. Haskell の仕様で、"ケース文を上から下にチェックする"という仕様が残っているのはなぜなの？ 最適化の邪魔では？
- if 文のネストを書くときのようにケース文を使うには、これは必要
- 「と同じになるように」
- 本にあるreverse の実装は遅い
- haskellは連結リスト
- consは早い(リストは永続するので、残りの部分を再利用できる)
- tail も早い。
- 末尾に値を加えることはできない(永続性が崩れる)。この場合はコピーが必要。
- 本のreverse の定義の ++ [x] は毎回コピーするのでヤバい
- ヘルパ関数reverse' を定義する。acc(アキュミュレイター)という引数を増やす
- acc に結果をためていく。結果としてconsだけで実現できる
- reverse = reverse' [] where reverse' acc (x:xs) = reverse' (x:acc) xs ...
- Haskell は遅延評価のために、末尾再帰はすこし複雑。
- reverse' は末尾再帰にならない。評価が残っているので
- Q. アキュムレーターって何？
- A. 返したい値を少しずつ集めるもの。集めた後に、最後に変換することもある。
- A. 末尾再帰だと、結果を捨てられる。なるべく末尾再帰に直すのがよい。その解決手段として、アキュムレーターを追加することがよく行われる
- アキュムレータ(acc)を第一引数にすると、カリー化が使えてよい。
発表：第7章 高階関数 / @imagawa_yakata さん
- 公開関数とは関数を引数・戻り値とする関数。ここでは前者
- リストを処理する関数 : or , sum など
- 例えば、リストに10未満の数があるかを調べるには？
- filter even [1 .. 5] (evenが関数)
- map (+1) [1 .. 5] (+1 が関数)
- 10未満の偶数があるかをチェック → or $ map even $ filter (\n -> n < 10)
- 合成演算子 : 「.」 → f . g = \x -> f (g x)
- sum のような感じで、関数を集約できる関数はないの？
- foldl → foldl (+) 0 [1 .. 3] : 0がアキュムレーターとなっている
- foldl (.) id [or, map even, filter (\ n-> n < 10)] はできるのかな？
- できない。Listの中身の型がバラバラ
- 同じ方の関数ならできる
第２部（演習）
えんしゅうするっぽいです。
- import Char は非推奨。import Data.Char
- リストの変数名の末尾には「s」を置く
- elem は `elem` の中置きの表記で書く。バッククォートは結合が弱いので、括弧が要らなくなることがある
- Hoogle を使うとよい。作ってるのはhlint を作った人。
- seq や ! を使って正格評価させて、数値を潰してスタックを食いつぶさないようにする
- ghcではBangPatterns プラグまで、引数に!をつけるようにできる
- モジュールのあるパッケージを特定するいい方法がない(Hoogleを使う？)。コメントにbaseやmtlなどと書くとよい
- -Wall をつけて、警告は全て消すとよい
- ghc で -O -ddump-simpl をすると、中間コンパイルの状態を見れる
- ++ は左の要素のみをコピーする。よって、[..]++([..]++[..]) を ([..]++[..])++[..] と書くと、コピーの量はO(n)からO(n^2)へ増える。
