読者です 読者をやめる 読者になる 読者になる

北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

今日は第2回スタートHaskell の日です

レポート haskell

第2回スタートHaskellに来ていますので、レポートします。といっても、中身は全てProgramming in Haskell の話なのですが。

宿題の解説 / @yuzutechnology さん

宿題の答え合わせ。

  • 問題2 : カリー化の問題。
  • 問題3 : フレームレートやビットレートの計算。
    • 非圧縮のサイズをレートなどから計算し、ファイルサイズと時間から単位をあわせて圧縮後のビットレートを出す。ただし、ビデオだけの計算なので音声の分を引く必要がある。
    • 音声のビットレートは圧縮率なの? → 議論は後から
    • fromIntegral ってのはわかるの? → 演習問題で出ていた。IntとFloatの型を合わせる。
    • ある型から自型へ変換するのは fromXXXX、自分の型からある型へ変換するのは toXXX
    • 型は合わせなければ成らないが、多相なのである程度だけ覚えておけば後は勝手にイイカンジの定義が使われる
  • 問題4
    • length が 4未満かの確認のコストは、長さによって変わるのでは? → その通り。長くなると不利。違う実装も考えられる
    • かっこ要らないのでは? → hlint をcabalで入れておくとよい(インストールに3時間くらいかかる)。構文的に冗長な部分があればアドバイスをくれるっぽい?
  • 問題5
    • この問題は必要とされる数学の知識のレベルが高い。今回からは数学の問題は少なめになる。
    • 各点が求められる平面上にあること、
    • 点が時計回りに配置されること
    • 外積ベクトルを出して同じ向きであること、辺のベクトルが外積と平行であること
    • Haskell では where で式をたくさん並べられる。順番に実行されるわけでもなく、そこが面白い

第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] なので
    • take 2 "hoge" は "ho"。文字列のリストは、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
  • 補足
    • RWHでは、先に再帰部を書き、下に基底部を書く
    • マッチする回数の多い方が上の方が効率がいい? → GHCだと、基底部を先に書いた物としてコンパイルされる
    • (RWH はスピードおたくが書いてるんだけど、その効果はなさそう)
    • 再帰再帰の度に型チェックがあるのがありがたい(なのでLISP再帰だとちょっと意味が・・・)
    • 最終的には再帰はなるべく書かない。foldやfilterやmapで力不足のときだけ。ただ、最初は練習した方がよい
    • なぜ再帰は書かないのか → 意味が分かりにくい。fold などの方が意味はわかりやすく間違いも入りにくい
  • Q. for がよくないってのはどういう話?
    • for のbreakやcontinue で型チェックはしてない
    • for の中でも、変数の型のチェックがあるのでは? → そこまで簡単だとそうだけど、複雑になると・・・
    • 関数と文(for)を比較しているのが問題なのでは → 大事なのは、全てが"式"である、ということ
    • for は構文であって副作用を期待しており、何を計算しているのかが不明確、ってことでは?
    • OCaml とかでは、forの中にはinitを返す式しか書けなかったりもする

発表:再帰関数(補足) / トラビスさん

  • factorial → 負の数を渡すと、無限ループ
    • これは"部分関数"という。終了しないのは危険なので、error を使った方がいい
    • n | n <= 0 = error "...negative"
    • ケース文にて、頻度が高い物は上にした方がいい*1 → n > 0 を一番上
  • Q. Haskell の仕様で、"ケース文を上から下にチェックする"という仕様が残っているのはなぜなの? 最適化の邪魔では?
  • 本にある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の中身の型がバラバラ
    • 同じ方の関数ならできる

第2部(演習)

えんしゅうするっぽいです。

  • 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)へ増える。

*1:先のGHCでは変わらないという説はあるが、さっきのはパターンマッチの話。また、最適化などで変わるかも