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