haskell-jp / mokumoku-online #76

諸々ちょっとずつ進めてました。makeMistakesToLearnHaskellの進捗を後ほど共有します。そろそろ関数型まつりの方に集中したいが、ついつい簡単なそっちを進めてしまう...
山本悠滋です。いつもどおり関数型まつりのスライドをボチボチ進めます。今日も何か用事が多くてあんまり時間が取れないかもですが...
Competitive programming in Haskell: cycle decomposition with mutable arrays: Brent Yorgey 先生の blog をもとに Kattis の問題を解きます
S.K.です。少し遅くなりましたが、今週もお世話になります。よろしくお願いいたします。
今週も引き続き Implementing Functional Languages: a tutorial, 5.4 Mark 3: A realistic parallel G-machine の続きを進めて行こうと思います。
少し進められました。ChatGPTに図を書くのを任せられないかと思ったけど失敗!
"Chair Hopping" 問題 考慮(苦慮)中 Permutation の Cycle decomposition は IntMap と IntSet を用いて効率的に出来たと思う(見かけ Yorgey 先生の mutable array による implementation に比べて遜色ない - 多分) しかしこれを用いて場合の数を組み合わせ論的に計算すると examples と合わない ??? もうちょっと考えよう
5.4.2 Conservative and speculative parallelism の Ex.5.15 の続きを進めようとしてました。
スパインに十分な関数適用ノードがない場合ということで、テストプログラム main = par (S K K) (S K K 3) の動作結果を確認してみたのですが、途中の K 3 (K 3) については (K 3) を評価しようとすることはなく、単純に引数が充足してないケースはエラーとなってしまうので、ちょっと行き詰ってしまいました。
ネットで検索すると、Haskell ではラムダ抽象やコンストラクタも WHNF とのことで、ラムダ抽象はパラレル G マシンでは使えない様なので、コンストラクタの場合について調べてみることにして、とりあえずリストを処理するテストプログラムを並列化して動作確認中です。
山本悠滋です。関数型まつりの資料を概ね仕上げて、時間を計るのと練習のために録画してみます
が、その前にお昼ご飯などの買い出しよ!
Competitive programming in Haskell: folding challenge: Brent Yorgey 先生の blog をもとに Kattis の問題を解きます
S.K.です。今週もお世話になります。よろしくお願いいたします。
今週も引き続き Implementing Functional Languages: a tutorial, 5.4 Mark 3: A realistic parallel G-machine の続きを進めて行こうと思います。
カマイルカ :dolphin: です。
今日は私も「関数型まつり」の発表準備に取り組んでいます(当日まであと2週間弱 :muscle:)。
Yorgey 先生のこの blog シリーズにどうやら Archive に漏れがあって この blog には前回の"Chair Hopping" 問題の答え合わせがナイ! 独力では歯が立たず Gemini 2.5 Pro (preview) にお手伝いをお願いして ナントカ回答に至るも WA 途中経過の正答は Test Cases: 13/34, Runtime: 0.31 s であった 前半の cycle decomposition は自己流でやった 10^9+7 Modulus は考慮していない これが原因とはちょっと考えニクイ (N <= 10^5) 後半は "On the number of even roots of permutations," Glebsky, Licon, Rivera () に依った これ移植が原因? Difficulty: Hard 5.8 あなどるべからず 誰か正解を知っていたら教えて下さい
今回の出題は "Origami" 問題 これも Difficulty: Hard 5.8 とあるが アイデアの段階ではそれほど難しくはナイ(はず) ただ(無限)直線と凸多角形の切断とか 凸多角形の内点判定とか コーナーケースが多くて煩雑になりがち 時間が掛かり苦手な奴 ひたすら実装をめざして労役中
資料仕上がらず!録音は手つかず!
5.4.2 Conservative and speculative parallelism の Ex.5.15 の続きを進めようとしてました。
リストを処理するテストプログラムを並列化した(つもりの)以下のプログラムの動作確認中です。

cons = Pack{2,2} ;
nil = Pack{1,0} ;
downfrom n = if (n == 0)
nil
(par (cons n) (downfrom (n-1))) ;
main = downfrom 2

スケジューリングせずに待たせておいた方が良さそうな部分は、まだ見つけられていません。
引き続き確認していこうと思います。
関数型まつりの発表準備、前提を説明する序論パートが仕上がって本論(例証)のパートを作り始めるところまで進みました(全体の進捗はまだ30%くらいなので引き続き頑張りたい :muscle:)。
第294回Haskell-jpもくもく会 @ オンライン ? Going today or cancelled?
... Replies ...
I'll do any way...
Competitive programming in Haskell: folding folds: Brent Yorgey 先生の blog をもとに Kattis の問題を解きます
ちなみに前回模範解答が無かった "Chair Hopping" 問題が解けました 部分的にしか解けなかった原因は Glebsky, Licon, Rivera の implementation bug でした これを Gemini 2.5 Pro (Preview) 先生と共同作業で fix 出来ました 難問解決にあたり AI aided programming は人間側の理解力と評価/実証力に大きく依存するのを実感しました
なお解の前段で cycle decomposition をする部分は IntSet/IntMap を使いました golf 的な簡明のうちに 性能は CPU Time 0.32 s の出来でした これを Yorgey 先生の UArray を用いた場合には 0.25 s に向上しました
S.K.です。今週もお世話になります。よろしくお願いいたします。
今週も引き続き Implementing Functional Languages: a tutorial 5.4 Mark 3: A realistic parallel G-machine の続きを進めて行こうと思います。
カマイルカ :dolphin: です。
先週に続けて準備に取り組みます(今日で完成させる :muscle:)。
ちょっと想像以上に昼寝が長引いてしまいましたが、関数型まつりの発表の練習をします。
Haskellとの関係が遠くなりますが、Scottさんの発表の動画が来てたら字幕を付ける件も時間内になるべくやりたい(が、動画がまだない!)
いずれにしても、ちょっとまだ別件を果たさないといけないので本格的にやるのは16時くらいからになりそうです :cold_sweat:
なるほど。ZapierかIFTTTが実行失敗してるのか...
自動投稿がないのは単純にIFTTTでの投稿に失敗しているだけなので、構わず始めてください。本当にキャンセルするときはアナウンスします。

IFTTTのログを見たところ、単に実行が始まっていないようにしか見えず、ちょっと原因が分からない状況なので、今後も発生するかもしれません。
うーん、終了のアナウンスも来ないな :disappointed:
関数型まつりの練習を兼ねて、万が一に備えた録音・録画をOBSでやってました。
途中でスライドに分かりづらいところを見つけて直すのに時間がかかってしまいましたが、2/3くらい終えました。
5.4.2 Conservative and speculative parallelism の Ex.5.15 の続きを進めようとしてました。
リストを処理するテストプログラムを並列化した(つもりの)以下のプログラムの動作をようやく一通りなめました。

cons = Pack{2,2} ;
nil = Pack{1,0} ;
downfrom n = if (n == 0) nil (par (cons n) (downfrom (n-1))) ;
main = downfrom 2

サブタスクの処理について、スパインの左端が Pack 命令を使った形にまで展開されて、スパインのルートノードが展開された式への間接参照ノードに更新されたら、そのサブタスクの処理は実質的に終了してるような感じに見えました。
スケジューリングを待たせるというよりは、NNum ノードへの間接参照ノードに更新されたときと同様に、サブタスクを早めに終わらせて他のタスクにプロセッサを明け渡すのが良いかもしれないと思いました。(それだと教科書の意図とは違ってしまいますが...)
ただ、コンストラクタを使った他のプログラムについても成り立つことなのか、まだよくわかっていません。他のテストプログラムについても当てはまるか確認してみようと思います。
宿題の"Origami" 問題は「多角形を折り返す」方針を変更し「点の mirroring に」して AC だった これは Yorgey 先生の解答とも一致
今回の問題 "Please, Go First" 考慮中 各々文字グループごとに連続になるよう並べ直す手数を計算し それらの和をとる方針 マッぼちぼちやりましょう
来週は(運営さんが開催と仮定して) :nichi: を希望
関数型まつりの発表準備で、関数合成についてHaskell, Scala, Clojure, Elixirの4言語での関連するサンプルコードを用意していました。
Project Eulerの問題を例に各言語で複数パターンのコードを書いていたら時間が溶けました :innocent: (他の話題のサンプルコードは軽めにしたい……)
今日はちゃんと動いた:relieved:
山本悠滋です。関数型まつりの発表も終わったので、makeMistakesToLearnHaskell and/or Haskell-jp Blohの続きをやります
Competitive programming in Haskell: monoidal accumulation: Brent Yorgey 先生の blog をもとに Kattis の問題を解きます
ちなみに宿題の "Please, Go First" はトンデモ問題で Kattis の判定がたった2つの testcases だけだった
もしかして Sample と同じ? 今回の Yorgey 先生の模範解答に照らし合わせて再判定します
S.K.です。今週もお世話になります。よろしくお願いいたします。
今週も引き続き Implementing Functional Languages: a tutorial 5.4 Mark 3: A realistic parallel G-machine の続きを進めて行こうと思います。
5.4.2 Conservative and speculative parallelism の Ex.5.15 の続きを進めようとしてました。
リストに次いで真理値を処理するテストプログラムを並列化した(つもりの)以下のプログラムの動作を確認していました。

f1 x = x == 1;
f2 x = x == 2;
f3 x y = x & y;
main = par (f3 (f1 1)) (f2 2)

まだ確認が少し残っていますが、こちらについてもサブタスクの処理について、リスト処理プログラムと同様の動作となっているようです。(考えてみれば当然のことだったかもしれません。)
スケジューリングを待たせるとサブタスクがいつまでも終了しなくなってしまいそうなので、教科書の意図とは違ってしまいますが、NNum ノードの場合と同様の方法を取ってみようかと思います。

あと、来週ですが土(6/21)日(6/22)とも用事がありまして、お休みさせていただきます。
再来週以降にまた参加させていただければと思います。
よろしくお願いいたします。
宿題の "Please, Go First" 問題は Yorgey 先生の模範解答および comments にある3人のコードとも いくつかのテストケースについて一致したので安心した
今週の問題 "Purple Rain" は maximum subarray sum と思われるが 実装に問題があるらしく WA だった 再度理論から復習して debug ぼちぼちやります
ちなみに Yorgey 先生のヒントは "ybbx hc Xnqnar’f Nytbevguz" これを ROT13 暗号として解読すると "look up Caesar's Algorithm" になるよし ナニコレ?
@Bora Savas has joined the channel
遅くなりましたが関数型まつりの合間に書いた本日のmakeMistakesToLearnHaskellの進捗。古いところを読み返しています
https://github.com/haskell-jp/makeMistakesToLearnHaskell/commit/ab3fdbc48d8d622c89c879e1e8d43b5e70111d17
Competitive programming in Haskell: Kadane’s algorithm: Brent Yorgey 先生の blog をもとに Kattis の問題を解きます
山本悠滋です。makeMistakesToLearnHaskellの続きやHaskell-jp Blogの続きをします。
先週の宿題 "Purple Rain" の先生の解は ”generalize it as much as possible” が徹底していて Int 型で良いものを newtype を使って Semigroup & Monoid 属性を持たされている コレはやり過ぎと思う ただし DerivingVia とか いろいろ勉強にはなった 徹底する人にはそれなりの Haskell 手法があるのね 感心した
今週の問題 "Modulo Solitaire" 考慮中 なんだか the Collatz Conjecture 風の数列停止問題 いろいろ実験しながら ぼちぼちアイデアがわいてくるのを待ちます
本日のmakeMistakesToLearnHaskellの更新。課題2の見直しまで終えたり、LTS Haskellを上げたりしてました。
https://github.com/haskell-jp/makeMistakesToLearnHaskell/commit/e3dc2f0c8aaaf0b9891b9863c00fdf094b4ffd1e
https://github.com/haskell-jp/makeMistakesToLearnHaskell/commit/89ed2c1ad35ecb9718e4d25daeb2b752e1616db0
Haskell-jp Blogの方は久々なんでちょっと分からなくなってる