haskell-jp / mokumoku-online #79

@ has joined the channel
Competitive programming in Haskell: parsing with an NFA Brent Yorgey 先生の (この謎の表題の) blog をもとに Kattis の問題を解きます
S.K.です。ちょっと遅くなってしまいましたが、今週もお世話になります。よろしくお願いいたします。
今週も Implementing Functional Languages: a tutorial の Chapter 6 Lambda Lifting の続きを進めて行こうと思います。
はじめまして。福島英人と申します。医学分野の研究室でゲノムの解析を行っている大学院生です。主にRでデータ分析をしており、今までコンパイル言語を使用したことはありませんし、プログラミング言語やアルゴリズムを深く理解しているわけではありません。

自分の目標は、自分でゲノムデータを自由自在に操り、複雑な解析用のツールをスマートなやり方で作れるようになること、そして基本的なアルゴリズムを美しい方法で理解することです。 

生物分野の解析では実はad-hocな解析・分析のほとんどがRかpythonで行われており、複雑なツールになると一部の単純処理のところにC++が入ってきます。
しかしHaskellはめったに使用されている例を見ません。 しかし、Rの解析においてもpurrrなど関数型チックなモジュール群が存在しスマートな方法でデータを整理することができたりします。これをより本格的な関数型言語で、整理された概念で学んでみたいと思い、この会に参加させて頂きました。

暫くの間は、Richard Bird の「HASKELL による関数型プログラミングの思考法」そして 「Algorithm design with Haskell」を実装しながら読んでいこうと思います。本日は前者の第一章をやります。そのうち、もっと他のこともできればいいなと思っています。お世話になります。
どうぞよろしくお願い申し上げます。
山本悠滋です。いつもどおりmakeMistakesToLearnHakellやHaskell-jp Blogの続きをします。
HASKELL による関数型プログラミングの思考法 第一章を、読み終わりました。
Competitive programming in Haskell: Chemist's vows なるほどね NFA とは Nondeterministic finite(-state) automaton のことで 遷移を丁寧に追うことで問題を deterministic finite automaton (DFA) に変えることが出来 (subset construction algorithm) これにて爆速を得る由 それで parsec と Text.ParserCombinators.ReadP.readP_to_S を使うのは余興となる ホント勉強になります 模範解を写経して 細かいが nub を Data.Set の S.toList . S.fromList に代えたら (0.09 s) で Yorgey 先生のそれ (0.22 s) より倍以上速かった
ただいま今週の課題 "Zapis" を考慮中
動作結果を元にテキストの 6.3.2 Free variables あたりからの説明を読んでいました。
freeVars 関数の動作は、少しずつ分かってきたつもりですが、まだ let(rec) の場合の処理がよく理解できていません。
とりあえずそのまま、6.3.3 Generating supercombinators に進み、abstract 関数の動作は理解できたつもりです。
そして、6.3.4 Making all the variables unique を読みながら、rename 関数の動作を理解中です。
自分にとっては中々難しいですが、時間をかけて理解していこうと思います。
山本悠滋です。今日はタイプセーフプリキュアの更新をして、その後余力があればいつもどおりmakeMistakesToLearnHakellやHaskell-jp Blogの続きをします。
Competitive programming in Haskell: Introduction to dynamic programming Brent Yorgey 先生の blog をもとに Kattis の問題を解きます
S.K.です。ちょっと遅くなってしまいましたが、今週もお世話になります。よろしくお願いいたします。
今週も Implementing Functional Languages: a tutorial の Chapter 6 Lambda Lifting の続きを進めて行こうと思います。
Competitive programming in Haskell: introduction to dynamic programming 読了 しかしこれは3連作の始まりに過ぎず 課題 "Zapis" を解くには TLE になってしまう それではという事で先生の blog の第2部 Dynamic programming in Haskell: lazy immutable arrays も読む事になり これを写本に ByteString を用いていた我が旧解を minor changes して Accepted  さらにメモ化を用いる改良版第3部 Dynamic programming in Haskell: automatic memoization があるそうなので これは来週のお楽しみ
クソ長昼寝をしてしまったので、まだ更新作業中です!
... Replies ...
動作結果を元にテキストの 6.3.4 Making all the variables unique の続きから、6.3.5 Collecting supercombinators まで読み、rename 関数と collectSCs 関数の動作を一応理解しました。
6.3.2 Free variables と freeVars 関数についても、letrec 式を使った以下のテストプログラム
pair x y f = f x y ;
f x y = letrec
fst = \p. p K ;
snd = \p. p K1 ;
a = pair x b ;
b = pair y a
in
fst (snd (snd (snd a))) ;
main = f 3 4
と、let 式を使った以下のテストプログラム
f x = let
g = \y. x*x + y
in
(g 3 + g 4) ;
main = f 6
を (freeVarse . parse) した結果を比較して、一応理解しました(つもりです)。
あと、遅ればせながら Ex.6.1 にも対応しました。
更新できました!Hackageにもアップロード済みです。
https://github.com/igrep/typesafe-precure/pull/68
Competitive programming in Haskell: Two more DP challenges: Brent Yorgey 先生の blog をもとに Kattis の問題を解きます
S.K.です。今週もお世話になります。よろしくお願いいたします。
今週も Implementing Functional Languages: a tutorial の Chapter 6 Lambda Lifting の続きを進めて行こうと思います。
山本悠滋です。昼寝で遅くなってしまいましたが、いつもどおりmakeMistakesToLearnHakellやHaskell-jp Blogの続きをします。
Competitive Programming in Haskell: two more DP challenges 読了 課題 "Honi" に挑戦 昼寝ボケか題意を読み取るのに四苦八苦 ChatGPT に "Sample Input/Out" の解釈をお願いした なるほどねと納得 コーディングをはじめたら スパゲッティが出来た 場合分けが多すぎる Yorgey 先生も "I don’t yet know how to write elegant solutions!" と言っていたのはこのことか? 呻吟再考中
makeMistakesToLearnHaskellの進捗: https://github.com/haskell-jp/makeMistakesToLearnHaskell/commit/327d875c9b40219bb650e51ee7c6dbb90c8b9949
Haskell-jp Blogの進捗はもう少し進めてから共有します
... Replies ...
Ex.6.2 を進めました。
pprintAnn 関数(下請け関数群を含む)と、とりあえず注釈処理用に iSet :: Set Name -> Iseq という関数を定義して、
以下のテストプログラム

f x = let
g = \y. x*x + y
in
(g 3 + g 4) ;
main = f 6

を parse して freeVarse した結果

[("f",["x"],(["x"],ALet False [("g",(["x"],ALam ["y"] (["x","y"],AAp (["x"],AAp ([],AVar "+") (["x"],AAp (["x"],AAp ([],AVar "*") (["x"],AVar "x")) (["x"],AVar "x"))) (["y"],AVar "y"))))] (["g"],AAp (["g"],AAp ([],AVar "+") (["g"],AAp (["g"],AVar "g") ([],ANum 3))) (["g"],AAp (["g"],AVar "g") ([],ANum 4))))),("main",[],([],AAp ([],AVar "f") ([],ANum 6)))]

を処理してみたところ、以下の様に表示されました。

f x = [x](let
g = [x](\y. [x,y]([x]([](+) ([x]([x]([](*) [x](x)) [x](x)))) [y](y)))
in [g]([g]([](+) ([g]([g](g) [](3)))) ([g]([g](g) [](4))))) ;
main = []([](f) [](6))

"+" や "*" は中置表記をやめて前置表記にしてみました。それでも、結構見づらいです。
はたして、これでいいのかどうかは、自分にとってはまだ不明です。あと case 式は未対応です。
Competitive Programming in Haskell: Two Hard Problems: Brent Yorgey 先生の blog をもとに Kattis の問題を解きます
S.K.です。遅くなってしまいましたが、今週もお世話になります。よろしくお願いいたします。
今週も Implementing Functional Languages: a tutorial の Chapter 6 Lambda Lifting の続きを進めて行こうと思います。
山本悠滋です。新型コロナワクチン打った後の体調不良で遅くなってしまいましたが、いつもどおりmakeMistakesToLearnHakellやHaskell-jp Blogの続きをします。
... Replies ...
Competitive Programming in Haskell: Two Hard Problems: 読了 与えられた2つの課題の一つ "Product Divisors" に挑むも あえなく TLE (16 個の testcase の早くも 3 番目で!) Difficulty: Hard 6.0 の問題に対して 愚直に素因数分解して τ 関数を計算しただけなので 当然の報いなのであるが さてどうしたものか? 思案投げ首
makeMistakesToLearnHaskellの進捗: https://github.com/haskell-jp/makeMistakesToLearnHaskell/commit/19528c50dc568ac2964a25d36d561a537969ee76
Haskell-jp Blogの進捗: https://github.com/haskell-jp/blog/commit/f143a5e9e7794f4a230dbab2c4925dc67f4838b5
後者がようやく一段落しました。最後の段落はほぼGitHub Copilotが自動生成したもので、やっぱこういうありふれた文を書くのはうまいですね。
Ex.6.2 の pprintAnn 関数は、この先あまり使われることがなさそうとのことで、動作確認をいったん保留して Ex.6.4 を進めました。(Ex.6.3 は一応対応済み。)
ラムダリフタを case 式にも対応させるとのことで、freeVars関数と abstract 関数の対応を済ませて、rename 関数の対応中です。
Competitive Programming in Haskell: Sieving with mutable arrays: Brent Yorgey 先生の blog をもとに Kattis の問題を解きます
S.K.です。ちょっと遅くなってしまいましたが、今週もお世話になります。よろしくお願いいたします。
今週も Implementing Functional Languages: a tutorial の Chapter 6 Lambda Lifting の続きを進めて行こうと思います。
外出中で今日はちゃんと参加できそうにないため、午前中に軽く進めた分だけ共有して終わりにします。
... Replies ...
Competitive Programming in Haskell: Sieving with mutable arrays 読了 先回の課題の一つ "Product Divisors" の解説だった STUArray を用いて最小素数因子の表を用意しておくこと (sieve) また因子分解の数え上げも別の STUArray を用いて行うこと (factor)  この2つが speed up の要点とのこと フムフム... かくて Yorgey 先生の結論は SPJ から引用して "Haskell, the world’s finest imperative programming language!"
Ex.6.4 の続きを進めようとしてましたが、途中から他事を始めてしまい、rename 関数を case 式に対応させたこと以外ほとんど進展ありませんでした。(しかも、動作確認は未完了。)
次回はこのようなことがないよう気を付けます。(反省。)
空き時間にHaskell-jp Blogも進めた。