Subscribed unsubscribe Subscribe Subscribe

HIMA' #3: Arrow(と随伴関手)

Haskell HIMA'

日曜日に3回目のHIMA'を開きました。今回のテーマはArrowとid:itto100penさん一押しの随伴関手でした。ベースとなるテキストは関数プログラミングの楽しみを使いました。
関数プログラミングの楽しみ

進行は僕が10章「アローと計算」を読み上げ、疑問点が出てきたところでid:msakaiさんとid:itto100penさんが解説するという形式で進めました。以下勉強会中にメモした記録+αです。

記録

  • pure = arrでOK?
    • OK
    • pureだとApplicativeと被ってしまう
  • 「入力とは独立した静的構成要素を持つ計算とは何か」
  • Arrow記法はHaskell 2010に含まれない
    • {-# LANGUAGE Arrows #-}が必要
計算の概念
  • 状態変換子
    • このStateはカリー化してflipするとStateモナドと同等
    • Arrow: (s, i) -> (s, o)
    • Monad: i -> (s -> (s, o))
  • 写像変換子
    • 具体例は?
    • addMT f g m sの定義が読みにくい
      • m :: s -> i
      • s :: o
  • 単純オートマトン
    • AutoはStateでは表せない
    • 再帰的な定義になっているところがポイント
圏および関手


  • mapは「関数の圏からそれ自身への関手」である
    • 一般的にはある圏から別の圏への関手となっているので、これは特殊な例
    • こういう関手をendofunctorという
  • pureは「純粋な関数の圏から新しい圏への関手」である
    • βとγが変わらないので、これも特殊
  • Homはhomomorphismの略。homset。
  • 積関手は英語ではproduct functor
  • p.219「しかしながら」の部分が読みにくい
    • 順序が変わると結果が変わってしまうので積関手を2つ定義しないといけなそうだけど、実際にはfirstがあれば1つですむ
      • 計算結果を次ではなくて、次の次に渡したい場合に、結果を保持しておく必要がある
  • 練習問題はどこかにアップロードしたら添削してもらえる?
    • OK
  • 練習問題10.4は何をすればいいのか
    • 原著から間違い: f |>< g = first f >>> arr (id *** g)
    • ↓を証明すればいい。この関手は(A, P) -> Aな関手。ここでAはArrowの圏、Pは純粋な関数の圏とする。

特殊な場合



    • 随伴とは、右の四角をたどれるなら左の四角もたどれて、逆に左がたどれるなら右もたどれることを指す
      • その片側だけが成り立つ場合を、右随伴・左随伴という
      • 各自復習しよう!
    • p.223下段「部分的に静的」とは何か
  • 条件分岐
    • p.225の中段「実際、任意のArrowApplyの」は「実は、任意のArrowApplyの」が適切
    • ArrowApplyにできるかどうかってどうやって判断できるの?
  • フィードバック
    • A New Notation for Arrowsにloopの公理のわかりやすい図がある
      • slidingで順番が変わるのはいいの?
        • arr kは純粋な計算なので問題ない。ここに一般のArrowを許すと順序を変えられなくなる。
      • loopとfirstの関係は?
        • 単ににているという話では?
アロー記法
  • 実際にアローを使うときは、まずアロー記法を使わないと面倒すぎる
  • 現在のGHCでは
    • 矢羽根(-<)以外に-<<もある
  • (| バナナ括弧 |)も使える
例題
  • 同期回路
    • 今年のICFP PCの回路もArrowで書くとすっきりするとか
    • 実例がないと難しいねとか
  • ここまで
    • 均質関数以降は時間切れ
次回

まとめ

  • Arrowはアロー記法を使って実際の問題を解かないと身につかないと思った
  • Arrow則は数が多いのでCoqなどの定理証明系を使う格好の題材ではないかと思った
  • 今回は随伴関手を覚えて帰りましょうということだったが、自分であの図を書けるようになるには、復習が必要
  • 第1回のiterateeも今回のArrowでも感じたこと
    • 当日ポカーンとしないためにも、予習はある程度必要
    • 時間切れで尻切れトンボになってしまうので、時間を長くするか、後で議論する場を設けたい
      • 元祖HIMAとしてchatonなりでやるのはどうか、とか
      • 今回のArrowに関して言えば、練習問題を解いて解答を公開するのはとても良さそう

以前から、how toだけでなく、背景も含めたHaskellの話ができる場があるといいなと思っていたので、今回のような勉強会が開けたことを本当にうれしく思います。快く講師役を務めてくださいましたmsakaiさんとitto100penさん、どうもありがとうございました。また会場提供のid:kazu_yamamotoさん、いつもありがとうございます。

次回はtanakhさんによる関数型的正規表現マッチということで、とても面白そうで期待です!