foo a b c = do
some a b c
foo a b c
と書くより
foo a b c = fix \go -> do
some a b c
go
みたいに書いたほうが、ほんのすこし見やすい気がする。
何かって言うと、foo a b cじゃなくてfoo a b' cみたいになってないかとか、そういうあたりに気をつかわなくてすむとかそういう。
ラピダスが「うまくいくかもしれない」って思うのは、EUV露光についてTSMCと共同研究してたのがIBMで、そのIBMの要請で創設されたのがラピダスだから(という素人談義)。
思うに、ここ10年くらいのIT系の進化がすごい気がするのだけど、これって王者がインテルからTSMCにシフトしたからってのもあるのかもしれない。
インテルはCPUしか作らないけど、TSMCはCPUでもGPUでも顧客が求めるものを作るので。
とりあえずDeflate圧縮のRunLengthの部分だけを実行した結果を32ビット整数としてファイルに保存する感じで使ってみるかな。
で、そのコードとハフマン符号化のコードを合わせればいい。
ハフマン符号の表を格納するのがめんどくさいので、まずは静的ハフマン符号化で全体を作って、それがうまくいったら動的ハフマン版を作ろうかな。
conduitのライブラリにByteStringに依存するモジュールを含ませるべきか、あるいはconduit-bytestringみたいに分けるべきか迷う。
conduitを使いたい場面は多くの場合ByteStringを使うと思うのだけど、ByteStringを使わない使いかたも、まあ、もちろん、ある。
で、bytestringはbaseに準ずるパッケージなので、まあ不要な依存が生じても実用上問題はない。
けど、まあ美しさから言うとconduit-bytestring的なパッケージに分けたほうがいいのかもしれない。
sequenceとかmap, setとかって、「内部的には木構造」だけど「意味的にはフラットな並び」なの、なんか面白いな。いろいろな操作を効率的にするのに「木構造」ってのはキーになる仕組みだ。
まずはさっき書いたgzipの解凍コードのRunlength部分だけ独立させて、RunLengthで圧縮した部分だけを試せるようにすることから、かな。なんか、なかなか食指が動かないな。
読み込む文字列からまず3文字ながめて、その3文字でハッシュ表を検索する。で、たぶんハッシュ表には「前に読み込んだ文字列中におけるインデックス」が値として格納されているので、そこから何文字一致するかを調べて、長いものを選ぶ。
そんな感じかな。ハッシュ表は一文字読み込むたびに成長させていく感じ。
per seってどういうニュアンスなんだろう。
https://datatracker.ietf.org/doc/html/rfc1951#page-14
deflate圧縮のpatent freeなアルゴリズム。読もう。
nostr:note10uwajt2zffpqt64s6fcfzcx6v90j35durce6agg39l4yshx2kxpqpcw9fg
zapは、めんどくさくて設定してなかったけど、後で試してみようかな。
type family TupleL t ts where
Tuple t '[] = t
Tuple t (t' ': ts) = TupleL (t, t') ts
みたいに定義すると、
(((((a, b), c), d), e), f)
が
TupleL a '[b, c, d, e, f]
みたいになるので、これなら複数行にしたときも、まあまあきれいに書けるかな。
runState的なものを連続して適用すると結果の型が(((((a, b), c), d), e), f)みたいになるのだけど、これが長くなって複数行にするときに、インデントをどうするかというのがわりとやっかいだ。
Deflate圧縮で無圧縮(00)のブロックは最終ブロックフラグと圧縮タイプの指定で3bit読み込んだあとで、そのあとバイト境界まで読み捨ててから、無圧縮データを読み込むのだけど、3ビット読み込む前の位置ってのは、バイト境界じゃない可能性があって、そうなってくると、いろいろとコードも面白いことになる。
突然のDeflate圧縮
なんか"'"(シングルクォート1個)という名前のファイルを誤って作ってしまいがちだ。
前段と後段に入れるRightでなかったときに例外を発生させるパイプを定義した。まだ使ってないので動くかどうかはわからない。
で、今書いてるdeflateのコードで言うならば、渡すデータがバイトの境界をまたぐかまたがないかで、Either BitArray ByteStringみたいなデータ構造でLeftかRightかを渡すようにしておいて、受け取る側では
Right bs <- get
みたいな形で、「人間はこれが失敗しないことを知っている」というコードの書きかたをするというのが、ひとつの妥協点かな、と。
さらに進めると、前段と後段のあいだに、Either BitArray ByteStringを受け取って、ByteStringを渡すみたいな処理を入れておいて、もしLeftが来たらエラーをthrowするようにするのもありかもしれない。
たとえば、
foo = do
[x, y, z] <- pure $ take 3 xs
みたいなコードを書いたっていいわけで、これは人間の目で見てfailになることはないのだけど、ちょっと気持ちが悪くもある。
でもプログラミングをしていると、こういう類の気持ち悪さをある程度許容しなくちゃならないことがある。
字面の美しさ、アルゴリズムの美しさ、効率、安全性といったいくつものパラメーターのなかでバランスを取る作業というのがプログラミングにはある。そこには楽しさと気持ち悪さとが共存している。
conduitという抽象を使ってコードを書いていて、その抽象だと前段で処理した内容を後段に渡していくわけだ。ここでは、その「前段」の部分がバイト列を続く処理にわたすのだけど、その前段の部分に「ビット単位」で値を渡す機能をつけるのも、「あり」と言えば「あり」だ。8の倍数でないビット数の情報を渡せるようにする、か。
でも、そのやりかただと2つ問題が出てくる。
1. 後段に渡すデータが単純なバイト列ではなくなる
2. もし1ビットずつ渡す形だと、毎回「バイトかビットか」「何個わたすか」をチェックするのが非効率
で2に関しては、ある程度大きいビット列を後段に渡して、それがそのビット列から1ビットずつ取り出して、次の処理に渡すというやりかたで問題ない。
後段に渡すデータが単純なバイト列ではなくなってしまう問題についてはどうしようかな。