Pixel Pedals of Tomakomai

北海道苫小牧市出身の初老の日常

今日はekmett勉強会の日です

ekmett勉強会に来ています。ekmettさんがオンライン参加されています。

I love profunctors. They're so easy / liyanghuさん

傘を指し棒に使うと言う斬新なプレゼン。詳細はこちら

  • HaskellのFunctorは共変
  • Predicate (a -> Bool) は Functor ではない
    • (半変)関手ではある
    • Data.Functor.Contravariant
    • contramap g (Predicate p) = Predicate (p . g)
  • 他、Const、Comparison (a -> a -> Ordering)、Op (b -> a)が反変関手
  • 双関手 : 引数を2つとる関手
    • bimap :: (a -> c) -> (b -> d) -> f a b -> f c d
    • Either、(,)、Biapplicative、Bifoldable、Bitraversable など双関手
  • Profunctor : 最初の引数が半変、次の引数が共変なだけ
    • dimap :: (c -> a) -> (b -> d) -> f a b -> f c d
    • Q. 「diって何?」 「dinatural transformationから」
    • -> はProfunctor (hom関手)
  • Limits' (a -> (b, b), a -> a -> Bool)
    • dimap g h (Limits step check) = Limits ((h *** h) . step . g) (check `on` g)
  • Indexed (i -> a -> b)
    • dimap g h (Indexed f) = Indexed (dimap g h . f)
  • さらにIndexable
khibinoさんによる日本語での補足
  • Functor はコドメインを変える機能
  • Allow は始域と終域が両方ある
  • Profunctor は Allow と同じ
  • Strongのfirst'とsecond'は、Arrowのfirstとsecond
  • ChoiceはArrowChoiceのそれと同じ

LensでHaskellをもっとかっこよく / its_out_of_tune さん

  • SetterとかGetter。JavaとかC#的な記述
    • 例えばタプル
  • ネストした値の中身を変更するのは大変
    • パターンマッチ NG
    • 関数合成 NG
    • タプルの要素数が変わると識別師を変えねばならない
  • (^.)、_1、_2、_3で操作
    • _1 . _1 のような合成が可能
  • (.~) で書き換え。_n が合成できるので、その恩恵を受けられる
  • (&) を使うとさらに楽に (flip ($) 相当)
  • 例: PointとLine
    • レコードを使えばPointを書き換えるのは簡単だが、Lineの中のPointを書き換えるのは面倒
    • フィールド名の前に_を付け、makeLensesするとレンズが作れる
    • 型変数が入っている型でも使える
  • Lensの作り方 (2値のtupple)
    • セッターは? f :: (a -> b) -> (c, a) -> (c, b) → Functorっぽい
    • 第二引数の操作にはfmapが使える
    • 第一引数の操作には Data.Traversable の traverseを使う
    • Setter型を定義する Setter (a, v) (b, v) a b
    • _1 f (x, y) = Id (getId . f $ x, y)
    • a .~ v = over a (const v)
    • ゲッターは? foldMapっぽい。FoldMapDefault
    • Getting型の定義
    • v ^. l = (foldMapOf l) id v
    • GetterとSetterを併せてLensの型を作れば完成
    • traverse は合成しても同じ性質を持つ。よって、 _n も合成できる
  • 実際のLensではMutator (Id)とAccessor (Const)を使っている
    • エラーの原因を掴みやすくするため
  • Lens、Getter、Setter、Fold、Action などが定義されている
    • foldMapOf、over
    • to 取得した値に関数適用できる
      1. ~、-~、*~、//~、&&~
    • (.=)、use : MonadStateでの利用
    • (+=) など普通に使える
    • (^!)とact
  • Lensの構成図の下層にはISOやEqualityがいるが、これは宿題
  • まとめ
    • Lensはすごいアクセサ
    • Traversableが起点
    • こわくない

基本的には余状態コモナドの余代数だから、大丈夫だと思います!
@hiratara

  • Q. パフォーマンスに影響は?
  • A. baseより速い場合もあるよ。unsafeCoerce 使ってるので。*1

Package: free / fumievalさん

  • 忘却関手の左随伴に関するライブラリ
  • Applicative、Alternative free → 使いどころは??
  • Functorからactionを作れる
  • Dialogの例
  • 使い方
    • IOを使うためには、wrapの置き換え。peel
    • 置き換えるには go = runF return peel を使えばよい
  • functorだけが必要で、functorもderivingできる
  • free-game
    • runGame :: Game a -> IO (maybe a)
    • Monaris 240行で実装したテトリス → デモ
  • cofree comonad → Functorからコモナドの自動生成
    • unwrap :: w a -> f (w a)
    • Cofree から 色々なものを作れる (Identityから無限Streamなど)
    • Lensとの組み合わせ → _extract、_unwrap、telescoped
  • Control.MonadPlus.Free
    • パーサコンビネータ実質5行程度で
    • functorは、入力1文字に対して何をするかを代数的データ型で
    • EmbededIO のようなコンストラクタを用意しとけばIOも挟み込めるよね
  • Q. functorにするものは操作を定義するってことであってる?
  • A. あってる
  • Q. functorを拡張した場合の問題は?
  • A. 特に問題はない
  • Q. パフォーマンスは?
  • A. 普通のfreeモナドはちょっと遅い。チャーチエンコーディングだとfmapが融合されて1個に。CPS変換。詳しい説明
  • Q. メモリは??
  • A. 組み方によっては。流れるような感覚で回避
  • Q. free-gameをfreeモナドを使わずに書くとどうなの?
  • A. 保守性が下がる。モナドをいじるのはfunctorを弄るのより大変。モナドを作る労力の削減ができる
  • Q. モナドを作るのは大変?
  • A. MonadStateとかMonadReaderとか定義するのは大変
  • Q. バックエンド変わった場合は?
  • A. GHCが将来androidに対応したら、とかあるでしょう
  • Q. cofree comonadの実用例は?
  • A. 時空射(chronomorphism)とか(使い方わからないけど)。構文木に注釈入れるとか

ad-3.4 / nebutaさん

  • MATLABやImageJは使いにくい → ScalaHaskell
  • 自動微分、テーラー展開、gradient、Jacobian
  • 記号微分にはsimple-reflect を入れる
  • import Numeric.AD して diff sin 0
  • Debug.SimpleRefrect → diff sin x とかできる
  • 関数の同値性も見れる(係数の違いで無理な場合も)
  • 自動微分についてはwikipediaとか見てね
  • 構造
    • Numeric.AD、NumericAD.InternalClasses
    • Numeric.AD.Mode.** モードの実装
    • Numeric.AD.Types 型の定義
    • diff :: Num a => (forall s. Mode s => AD s a -> AD s a) -> a -> a
    • tangent :: Num a => AD Forward a -> a
    • bundle a -> a -> AD Forward a
    • apply :: Num a => (AD Forward a -> b) -> a -> b
    • newtype AD f a は f a。fはModeのインスタンス
    • AD s a はFloat のインスタンスなんで、それっぽく読んどけばOK
  • apply は AD Forward a に a -> b を適用する
  • ADはLiftedとModeのインスタンス
  • deriveNumeric Liftedのインスタンスに数値型を定義
  • ハマりどころ → 自動微分させるには多相のままにする必要。
  • 要望
    • 微分した時の
    • 100次とか50次だと終わらない
    • 積分は?
  • (ここでekmettさんが激しく解説して下さったけど内容理解できず)
  • Haskellの簡潔さはわかりやすい。GHC拡張が多くて大変だった

Machines / halcat0x15a さん

  • scala-machinesに興味あり
  • Stream processing library by @kmett, @runarorama
  • Machine(入出力)、Plan、Process(変換)、Source
  • Step k o r : k 入力、o 出力、r 結果
    • Await 入力適用、Yield 出力、Stop 終端
  • Plan → チャーチエンコーディングされたものだが、基本DoneとYieldとAwaitとFail
  • repeatedlyとawait、yieldでProcessを定義。sourceはconstructでSourceを定義
  • Isクラスで型のチェックを定義
  • (~>) (<~) でMachine(Source | Process)とProcessを結合
  • Automaton autoで射をProcessへ持ち上げられる
  • Tee、Wye → 入力の選択ができるようになる
  • SourceT、ProcessTではliftIOが使える
  • MachinesではI/Oはサポートしてない (Conduitとの比較)
  • Q. なんでPlanとMachineが必要?
  • A. Monadにできないから? → 「0.3ではMachineはMonadになるよ」
  • scala-machines
    • モナド変換子はない、Driver + Procedure
    • Driver インプットを処理
    • Procedure Driverを走らせる

Trifecta / Parsers / tanakh さん

  • パーサコンビネータ
    • Trifecta とは? : Iteratee、Parsec、Monoidal Parsing
  • パーサライブラリ
    • parsec(デファクタ)、attoparsec(速い)、binary(hakell platformにも、generic-derivingにも)、cereal
    • iterateeとかconduit、attoparsec-conduit
    • peggy (Template Hakellのコードを生成する Template Haskell)
  • 何が新しいの?
    • ParsecとMonoidal Parsing を融合
    • Parsecは便利。Monoidal Parsing は 並列、インクリメンタル
    • APIがいい。トークンの扱い
    • CPS変換、標準的なAPI(FUnctor、Applicative、Monadなど)、エラー処理がいい
  • AlternativeとApplicativeで標準的なパーサが定義されている
  • TokenParsingはCharParsingに基づいている
  • Iteratee的なインタフェース
    • Lazy Stringを受け取るインタフェースは良くない → IOのエラーとかで落ちてしまう
  • clangスタイルのエラー報告
    • 「^」とかシンタックスハイライトととか。parsecよりわかりやすい
  • parsers : パーサコンビネータの一般的な操作の型クラス
    • trifecta は則ってる
    • parsec-parsers もある
    • attoparsec-parsers も誰か書いて
  • 2分でJSON parserを書くデモ
  • Q. パフォーマンスは?
  • A. attoparsecの10%程度。Parsecとなら勝負になる → 「1/8に改善する予定だよ! attoparsec並のモードも搭載予定」

軽い気持ちでtablesを使ってみました / yugaさん

  • 同梱されているFoo.hsも参照
  • CSVファイルをDBに入れてみる
  • 0で埋めておくとオートインクリメント
  • makeLensesWith
  • テーブルにするためにはTabularをインスタンス
  • インデクスの定義
    • カラムの型 : Primary, Supplementalなど
  • primary で主キーを指定
  • デモ
    • conduitでCSVを流し込む
    • withで条件指定して、subsetを取り出せる
    • emptyで上書きすれば行削除
    • (^@..), group でグループ化
  • 3万行のデータでデモ
  • Q. joinはできるの?
  • A. まだprojectionの方法もわからない
  • Q. どんな構造で保持してる?
  • A. IndexはMap。
  • Q. DBとどう使い分ける?
  • A. tablesは小回りが利く?かも? バックエンド対応が進めば。「analyticsがDB用だよ!」

ekemett/speculation / ma0eさん

  • Safe Programmable Speculative Parallelism
    • C#の論文。実装はcoming soon のまま
    • 発表の次の月にekmettさんが実装したらしい
  • Specuration 投機実行
    • Lexing、Huffman decoding 逐次的にしか実行できない
    • 推測値を元に投機実行させるという話
  • spec :: a -> (a -> b) -> a -> b
    • spec g f a
    • aの値を計算し始める。gが推測値。
    • 先にf gを計算する
    • aとgが等しければf gをそのまま使う。違ったら f a を計算開始
    • ghcの7からは、f gをkillできるようになった
    • 負荷が高い場合は、f $! aと同じ動き
  • `par`で実装
    • sparkスレッドが`par`の第一引数を実行
    • ghc7から、sparkが不要になった時点でgcするようになった
  • unsafeIsEvaluated : 値が評価済かチェック。aがすでにわかってれば投機実行しない
    • tag-bitsにて定義されている
  • numCapabilities : 使えるコア数をチェック。1コアなら投機実行しない
    • 新しめのghcで使える関数
  • STM版もある。retryする
    • unsafeIOToSTM numSparksをnumCapabilitiesを比べて、投機実行を制御
  • C.C.Speculation.Foldable とか Traversableとか
    • foldrしながら投機実行を頑張る
    • g :: Int -> b : i番目が b かも
  • MonadSpec → ユーザ定義Monadにspeculationを!
  • 例: lexingの投機実行
    • 文字を分割して並列実装
    • HTMLの性質から、ほとんどの場合contentになる
    • 試しにHaskellで実装してみたら、めっちゃくちゃ遅くなった
  • どうやったら速くなるの? → 「粒度が小さ過ぎでは? 後で見てみるよ!!」
  • Q. 他に応用は?
  • A. 焼き鈍し法
  • Q. 先ほどの例でチャンクのサイズは?
  • A. コアが空いてれば仕事が分割される
  • Q. 入力から予測する部分のヒューリスティックじゃない方法って?
  • A. 確率的な方法でやる論文がある。予測の精度がパフォーマンスの鍵
  • Q. 複数ステップを同時に予想するのは? 3状態なら3つ走らせればいいんじゃね?
  • A. できるかも

The Reflaction Package / mkothaさん

  • 型を引数として利用するためのライブラリ
  • 整数をエンコードした型があれば、Modは定義できるが
    • Boolなら簡単。Intでも頑張れるけど・・・
  • Reifiesクラス
    • GHCの内部表現を使う。多相は DICTIONARY_Reifies としてコンパイルされる
    • unsafeCorerce で無理矢理辞書を作って食わせてもよい
  • ADの実装で使われている
    • Reverseモード
    • グラフを保持する必要があるが、そこでIORefを取り出している。
    • ユーザからは見えないようになっている

Bound / pad_techさん

  • "locally-nameless" terms (De Bruijn Index)
    • 数字で束縛変数を表す
  • lambda、forallのASTを書いたりするとき
  • scala-bound 今週突然産まれた実装
  • モナド変換子だけで実装
  • ここからはekmettさんのスライドで
  • 名前があると、被ったり、α変換とかめんどい
  • これらを解決する実装は色々ある
    • Naive Substitution → 代入時に変数名を変える。シンタックス奇麗だけど遅い
    • Barendregt Convention → 絶対ユニークな名前を使う。α変換は解決できない。名前作る必要ある。名前が長くなる
    • Higher Order Abstract Syntax → bindingをHaskellの関数にする。速い。定理証明器使えないし不自然
    • Cylon Detector → FreeとBound(数字)に分けた実装。α変換は(==)で十分。代入時に番号のインクリメントが必要。モナドは作りやすい。不正な項も定義できる
  • succ したくない → 再帰で定義
    • (>>=)が代入処理となる。もぐってsuccするので、O(n)が必要
  • succ は頭にだけ付ければ十分なはず。Freeぽくする
    • rank-2多相で解決する論文はある
    • return で済ませることができる。
  • bindをなんとかしたい。パターンマッチとか、一度に複数の値をbindとか
    • Boundクラスで抽象化
    • Letを定義に入れる
    • 弱頭正規形にも簡単にできる
    • 閉じてるかはTraversalで簡単に
  • ポリモフィックリカージョンの問題がある。Eqの定義がたくさん必要
  • 今後はhigher orderな方向性
  • まとめ : 2つの論文のアップデート、MonadとTraversableを定義すればよい、不正な項は定義できないよ

ekmettさんの質問コーナー

聞き取れてません、すみません。

*1:124箇所あるらしい