競プロ入門者 (Haskell 盆栽 1) → 茶色が遠い (・ω・)
シングルスレッドの神に会いたいか!?
情報収集
リンク
-
AtCoder
国内の競技プログラミング運営社 -
蟻本
ガチ勢向けのアルゴリズム本 -
AtCoder Clans
情報収集に (問題をダウンロードする CLI ツールなど?)
レートについて
レートの上げ方
過去問をたくさん解く
コンテストについて (AtCoder)
水色を目指すなら、 ABC に出るだけでも良さそうです。
ABC (atcoder beginner contest)
- 毎週土曜の 21:00 に開始
- 制限時間は 100 分
- 問題は A ~ H の 8 題
- レート制限は 2000 まで
ARC (atcoder regular contest)
- 毎週日曜の 21:00 に開始
- 制限時間は 100 分 or 120 分
- 問題は A ~ F の 6 題
- なんか難しそう
その他
- 問題毎に使用言語を変えることはできる?
たぶんできそう
その他リンク
-
tourist
世界最強の人
おや、兄貴の様子が……?
なんか兄貴さん (実兄) が蟻本を買っていてテンション爆上がりですよ! 競プロに絞れば全然僕にも勝てるので頑張ってほしいです。
お遊びレベルで C++ を始めるとのことで、 cppmap を薦めたら、早速初心者向けの 2 冊を購入していました。いいですね
ABS (Atcoder beginners selection) で入門開始
とりあえず リポジトリを作りました 。動的計画法の 1 番簡単な問題も解けない自信があるけれど、完答できるのだろうか……?
経過としては、 Haskell のコンパイルエラーから『何かが間違っている』雰囲気しか読み取れません。また全探索の解答しか思いつかないという状況です。
解答後は『AtCoder Beginners Selection を Haskell で 』を参照したいと思います。僕も ByteString
を使いたいですね。 Haskell 盆栽 70%, アルゴリズム 30% ぐらいの割合で学習できたらちょうど良いと思います。
謎の WA (wrong answer)
`stack` の話
ローカルで動くコードが提出時には動かない。一体何が……?
$ stack ghc -- --version
The Glorious Glasgow Haskell Compilation System, version 9.0.2
ぐああああああああ!
8.8.3 のつもりで 9.0.2 を使っていた!
$ stack config set resolver ghc-8.8.3
/Users/tbm/dev/hs/abs-hs/stack.yaml has been updated.
$ cat stack.yaml
packages:
- .
resolver:
compiler: ghc-8.8.3
$ stack setup
stack will use a sandboxed GHC it installed
For more information on paths, see 'stack path' and 'stack exec env'
To use this GHC and packages outside of a project, consider using:
$ stack ghc -- --version
The Glorious Glasgow Haskell Compilation System, version 8.8.3
これでいけるか……?
$ stack build
ghc: panic! (the 'impossible' happened)
(GHC version 8.8.3 for x86_64-apple-darwin):
Prelude.chr: bad argument: 1543503875
Please report this as a GHC bug: https://www.haskell.org/ghc/reportabug
-- While building simple Setup.hs (scroll up to its section to see the error) using:
/Users/tbm/.stack/programs/x86_64-osx/ghc-8.8.3/bin/ghc-8.8.3 -rtsopts -threaded -clear-package-db -global-package-db -hide-all-packages -package base -main-is StackSetupShim.mainOverride -package Cabal-3.0.1.0 /Users/tbm/.stack/setup-exe-src/setup-mPHDZzAJ.hs /Users/tbm/.stack/setup-exe-src/setup-shim-mPHDZzAJ.hs -o /Users/tbm/.stack/setup-exe-cache/x86_64-osx/tmp-Cabal-simple_mPHDZzAJ_3.0.1.0_ghc-8.8.3
Process exited with code: ExitFailure 1
なんだぁ…… stack
から cabal-install
に移行しろということなのか ……?
続行
謎のエラー解決
キャッシュが? 残っていたようです:
$ rm -rf ~/.stack
$ stack setup
$ stack build # 成功
ちなみに GHC 8.8.3 用の HLS (1.5.1) ではシンボルのリネームができませんでした。プロジェクト毎に HLS のパスを差し替える方法も考えないといけません。保留……
WA 解決
後方互換性が原因でなかったようです。GHC のバージョンを 8.8.3 にしても正常に実行できました。
ず〜〜と原因を探していたら、 YES
ではなく "YES"
を出力していました。目でチェックすると脳みそを貫通する〜〜
ABS 1 周しました
意外と難しかった……。 難度 問題 C までなら全探索でも AC になる (ことがある) というのが分かりました。
AtCoder Beginners Selection を Haskell で を見て効率化を目指しつつ、今晩の ABC に備えようと思います。
レート戦 1: ABC 255 惨敗
Haskell 盆栽が辛い。最初の 2 問を解くのに 55 分もかかりました。実戦でモタモタするのは意外に悔しいことが分かりました。
『パフォーマンス』は 700 らしいですが、どういう値か分かりません。 レートは 42 になりました*。なんともネットミーム感のある値……w 解答を見つつ、盆栽慣れとアルゴリズム力強化を並行してやっていきたいと思います。
コマンドラインツール導入
atcoder-cli + online-judge-tool を導入しました (リポジトリ) 。テストが楽になった他、解答提出も acc
(atcoder-cli) で可能です。
現状のテンプレート:
#!/usr/bin/env runghc
module Main (main) where
main :: IO ()
main = do
xs <- map read . words <$> getLine :: IO [Int]
print $ solve xs
solve :: [Int] -> Int
solve xs = undefined
コンパイルせずに (?) runghc
で実行しています。依存パッケージなどを考えると stack
か cabal-install
? で管理できた方が良さそうですが、様子を見ます。
ペール本 1
関数プログラミング 珠玉のアルゴリズムデザイン
この本を読めるようになることが、 Haskell で競技プログラミングを始める最大のメリット?!
1. 最小自由数
リストに無い最小かつ 0 以上の整数を求めます。
Array による解法
まず Haskell の Array は特殊で、フィールド?は定義域と [(kev, value)]
です。 Vector
でよくないですか?
accumArray も大変な関数でした:
$ ghci
Prelude> import Data.Array
Prelude Data.Array> :i accumArray
accumArray ::
Ix i => (e -> a -> e) -> e -> (i, i) -> [(i, a)] -> Array i e
-- Defined in ‘GHC.Arr’
使ってみると理解できます:
Prelude Data.Array> accumArray (++) "a-" (1, 7) $ zip [3..5] (replicate 3 "b")
array (1,7) [(1,"a-"),(2,"a-"),(3,"a-b"),(4,"a-b"),(5,"a-b"),(6,"a-"),(7,"a-")]
しかし理解したって何のリターンも無いですよ! 高揚してきました。
コードの書き方も良くない部分がありました。特に replicate
をフィルタリング (0 なら有、 1 なら無) に使っていたのは良くないと思います。 mapMaybe
(filter_map
) の方が意味が明確です。
逆に良い点は数学的で厳密な言葉遣いです。
分割統治法による解法
単なる 2 分探索です。 partition
の計算量が最大
2. 上位者問題
運算でトップダウンに式変形して分割統治法を実装します。ボトムアップでよくないですか……? 検討中
3. 鞍型探索の改良
む、難しくて何が書いてあるのか分からない!
Union-Find
頻出らしいデータ構造に関する アルゴ式のページ をペラペラと読んで来ました。全ページサクっと読めて素晴らしいですね。蟻本を見たら、栞の 20 ページくらい先に載っていてモチベーションになりました。
環境構築 3
Stack script で import するとき、
- HLS 上で認識
- 実行に成功
今夜の ABC は言語サーバオフで参加するしかない。。
package.yaml
の executables
を書くとちゃんと補完してくれました。うーむ
ABC 256 惨敗
レート戦 2:前回からの進歩
-
Haskellで戦う競技プログラミング を読んだ
Vector
,ByteString
,runST
の初歩を学んだ (たぶん人のコードが読めるようになった) - コマンドラインツールでテストケースをダウンロードできるようにした
- 関数型プログラミング 珠玉のアルゴリズムデザイン を 2/30 読んだ
結果
項目 | データ |
---|---|
正答数 | 3 問 / 8 問 (600 点 / 3200 点) |
レート変動 | 42 → 102 |
パフォーマンス変動 | 700 → 497 |
所感
ぐああああああああああああああああああああああああああああああああああ
誤答のペナルティが痛かった……。でも D 問題までは Haskell に慣れるだけで解ける気がします。アルゴリズム力が問われるのは E 問題からでしょうかね。
リストから Vector に乗り換えたい投稿 (WIP)
これで D 問題の TLE を避けられたら今週は優勝! ← ボトルネックは、むしろループの書き方でした。
標準入力
Haskell で解く AtCoder が良さそうです。
固定長配列は無い
固定長配列の Vector を持ちたい! Haskell に固定長配列は無い。替わりになるものは?:
-
LTS 16.11 には
Data.Vector.Fixed
が無かったよ! - タプルは遅延評価が怖そう。使い勝手も悪そう
-
Array
はヒープに配置される気がする -
repa
は大変そう
とりあえずリストでいいか……。
リスト内包表記
Stream Fusin の恩恵を受けながら組み合わせを列挙するには? WIP
再帰
スライスはある? WIP
ABC 256 D 問題の AC
人の関数をコピペして TLE を突破 (?) してみました。真の AC は遠い……なお公式の解説は 単なるループ で処理していました。 Haskell においても、単なるループになるように再帰関数を書けば良かったのですね。 (書けませんでした)
次回までは、蟻本を読みつつ過去問の A ~ D 問題を解いてみようと思います。もしくは積み本崩しに逃げます。
レート戦 3: ABC 258 圧倒的惨敗
1 問しか解けませんでした。 Haskell 難し過ぎる……競技プログラミング以前の壁があまりに分厚いです。つらいよ!
項目 | データ |
---|---|
正答数 | 1 問 / 8 問 (100 点 / 3200 点) |
レート変動 | 102 → 137 |
パフォーマンス変動 | 497 → 362 |
次回までにやりたいこと
エディタサポートを強くしたいと思います。現在は、 Haskell のバージョンを下げたせいで言語サーバの機能が弱まっています。せめて変数の型はまともに判定したいです。 Slack で聞こうかな。
今回は実力不足を思い知りました。蟻本を読みつつ、 A ~ C 問題に絞って解いてみようと思います。この辺の問題は Rust なら一瞬なのですが、今しばらくは Haskell だからこその味を追い求めてみたいです。
追記
問題 B を読み違えて DFS の問題だと思っていました。ダメ過ぎる!!
レート戦 4: ABC 259 惨敗/好転の兆し
所感
文法エラーで詰まることは無くなりました。今は実装力が足りません。
- B 問題: 小数の精度で死亡
- C 問題: 読解力不足、知識不足 (
group
/groupBy
に気付かなかった) - D 問題: 明らかにグループ分け問題だが union-find 木が書けなくて死亡
パフォーマンス
そろそろ色変を狙っていきたいですね (成績から目を逸らしながら)
項目 | データ |
---|---|
正答数 | 2 問 / 8 問 (300 点 / 3200 点) |
レート変動 | 137 → 166 |
パフォーマンス変動 | 362 → ? |
次回まで
解き方が分かる問題は実装できるようになりたいです。ST モナドと mutable vector を試してみるか、人の解答を読みます。
ABC260 辛勝
レート戦 5:D 問題まで行けなかった のですが、心理的には勝利です。 B 問題がキツかった……
所感
- A 問題: 読解力が必要
- B 問題: Haskell では難しい。データ数が増えたら死んでた
- C 問題: 単なる再帰 (ただし整数の桁数制限に気をつける)
パフォーマンス
全然ダメか……。 提出時間で大幅にパフォーマンスが変わる ような気がします。
項目 | データ |
---|---|
正答数 | 3 問 / 8 問 (600 点 / 3200 点) |
レート変動 | 166 → 217 |
パフォーマンス変動 | ? → 579 |
次回まで
次こそは、出場した ABC の D 問題 (5 問) を解きたいと思います。
ABC261 もうダメかもしれない
レート戦 6:所感
- A 問題: あああ
- B 問題: グアアあああああ
- C 問題: ホワァアアアアアアアアアアアアアアアアアア
所感
- A 問題: 算数ができなくて死亡
- B 問題: 連結リストや Char の boxing が遅すぎて死亡
- C 問題:
hashtable
と思ったが Haskell が難しくて死亡
パフォーマンス
項目 | データ |
---|---|
正答数 | 2 問 / 8 問 (300 点 / 3200 点) |
レート変動 | 217 → 208 |
パフォーマンス変動 | 579 → 191 |
次回まで
明日は復習だ!
レート戦 7: ABC262 末期
VU.Vector
は多次元配列には利用できないという罠がありました。たぶん Array
を使うのが定石ですね。
所感
問題 | 所感 |
---|---|
A 問題 | 捻りなし |
B 問題 |
Data.Vector.Unboxed.Vector [Int] の罠で死亡 (作成以外の関数の制約を満たさない?) |
C 問題 | TLE. Vector は使えたので、単純な算数力不足の気がする…… |
パフォーマンス
項目 | データ |
---|---|
正答数 | 1 問 / 8 問 (100 点 / 3200 点) |
レート変動 | 208 → ? |
パフォーマンス変動 | 191 → ? |
次回まで
Array
を使えるようになろう。。
レート戦 8: ABC264 勝利
前回から
何もしてない……。
所感
今回は易しかったです。前回の反省を活かして、 2 次元の Vector
を作ろうとせず Vector.Unboxed.concat
しました。
問題 | 所感 |
---|---|
A 問題 | 捻りなし |
B 問題 | 捻りなし マンハッタン距離 |
C 問題 | 全探索 |
D 問題 | ? 時間切れ |
単純に Haskell が書けなくて C 問題で苦戦しました。
パフォーマンス
項目 | データ |
---|---|
正答数 | 3 問 / 8 問 (600 点 / 3200 点) |
レート変動 | 213 → 241 |
パフォーマンス変動 | 258 → 470 |
次回まで
C 問題、 D 問題の他ユーザの解答を読みます。
解答読みなど
C 問題
サブマトリクスを作って比較する解答が一番綺麗でした。リストを使わない場合は僕の解答で良さそうです。
D 問題
自力で解けそうです。 C 問題に時間かけちゃったからなぁ…….今回は本当に易しかった気がしますね。
- atcoder を 0123456 に置き換えてみる
- n 回の置換を n 個隣接した地点への移動として捉える
- 最も距離の遠い文字から順に移動させる
ABC265 敗北
レート戦 9:前回から
ほぼ何もしてない……。勉強量は成績に如実に現れるものですね。
所感
問題 | 所感 |
---|---|
A 問題 | 捻りなし |
B 問題 | なんか全部 AC になって本気で分からん…… |
C 問題 | グリッドは得意分野 |
D 問題 | 効率よく解けたはずが TLE |
パフォーマンス
項目 | データ |
---|---|
正答数 | 2 問 / 8 問 (400 点 / 3200 点) |
レート変動 | 241 → 250 |
パフォーマンス変動 | 470 → 328 |
次回まで
B 問題、 D 問題の人の解答を読みます。
> コンテスト開始5分以内にRatedで登録しない場合は、自動的にUnrated扱いとなります。
コンテストには時間通り参加しましょう……
スキルアップの方針
未だ C 問題でも解けないことがあります。 1,000 問くらい解けば水色になれるらしい ので、単なる演習不足と思います。できることとしては、
-
Qiita で ABC の解説 (Haskell) を挙げてくれている人がいる ので写経する
他人の解答は必須です。自分の頭はバグっていて、 2 分探索を始めたら永遠に制御が返ってこないこともありました。 どうせ解けないなら写経した方がマシ です。Array
など、見知らぬライブラリの使い方も身に付くと期待できます。 -
問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 の一部問題を解く/解き直す
余り計算や素数判定などの基本的な算数、動的計画法や貪欲法などの基本的なアルゴリズムを身につけます。しんどいけれど片手間でやっておく必要はあります。 -
競プロ典型 90 問 をやってみる
たぶんアルゴリズムのカバー率が良いのでやってみるべきではあります。蟻本を読むより、蟻本でカバーされるような問題を解いて身につけるべきと思います。 -
競技プログラミングの鉄則 (解説記事) を読んでみる
アルゴ式をやればいいのですが、 web サイトを継続的に読むのが苦手なので本を読んでみます。
どれかがアタリだと良いのですが。
Array vs boxing vector
ABC 270 C では、入力を受けてグラフを作成する必要があります。 Mutable な 2 次元配列が必要だと見て死にました。一生 Haskeller にはなれないのかもしれない……
ABC 270 C の Haskell 解答例 では accumArray
を使った解答が挙がっています。これが Haskell における典型的な解答であることは理解しています。しかし Array はメモリの使い方が良くないので、 Vector の解答を作って 比較してみました。差分はグラフの生成のみです:
Array による解答 (404 ms)
abc270c :: Int -> Int -> Int -> [(Int, Int)] -> [Int]
abc270c n x y uvs = fromJust $ loop 0 y []
where
-- flat map in Haskell is `>>=`.
graph = accumArray (flip (:)) [] (1, n) (uvs >>= (\(u, v) -> [(u, v), (v, u)]))
loop p c log
| c == x = Just (x : log)
| null ns = Nothing
| otherwise = msum $ map (\n -> loop c n newLog) ns
where
-- neighbors of the child
ns = filter (p /=) (graph ! c)
newLog = c : log
Vector による解答 (398 ms)
solve :: Int -> Int -> Int -> [(Int, Int)] -> [Int]
solve n x y uvs = fromJust $ loop 0 y []
where
graph = V.create $ do
-- +1 for 1-based index
vec <- VM.replicate (n + 1) []
forM_ uvs $ \(u, v) -> do
VM.modify vec (v:) u
VM.modify vec (u:) v
return vec
loop p c log
| c == x = Just (x : log)
| null ns = Nothing
| otherwise = msum $ map (\n -> loop c n newLog) ns
where
-- neighbors of the child
ns = filter (p /=) (graph V.! c)
newLog = c : log
どちらでも良いことが分かりました。 Array も mutable vector もまともに使った……もといコピペしたのは初めてです。 特に boxing な mutable vector を得たのは 銀の弾丸 感が凄い。次の C 問題は強引に突破できるかな……?
一歩一歩が非常に重いのですが、鉄則本の練習問題を含め、前に進んでいきたいと思います。
repa
は unboxing らしいのでaccumArray
の代わりにはなりません。
モナドへの興味
Data.Vector.Unboxed.create の中で mutable vector 以外の可変変数を作れなくて困ったことがありました。これは do 記法の中が ST モナドか何かのチェインになっていたためだと思います。
すべてを IO モナドにするみたいな抜け道と、『モナドの設計』のような成功法、どちらにも興味が湧きます。 Haskell ならではの味が少しだけ見えてきました。
- ST = state thread
-
runST
は Haskell の型システムを上手く使って内部の ST 値を外部に漏らすことを禁じている (何も制約が無いことを制約にすると、外部に接することで生まれる制約をコンパイルエラーにできる?) -
PrimState
モナドはIO
,ST
のどちらでも利用可能な API を作るために利用できる
標準ライブラリ
sortBy
[DONE]
sortBy
の使い方は 3 冊の Haskell 入門書にも載っていませんでした。まあ sortOn
とか Down
が使えれば十分かな……
アルゴリズム
2 分探索 [DONE]
ソート済み配列を OK / NG に区切って境界を見つける方法が有名みたいです。
エッジケースを Maybe
で処理してみました。もう少し綺麗になってほしい……
bsearch
-- | Binary search for a sorted items which returns the `(ok, ng)` index pair at the boundary.
-- |
-- | Example
-- | -------
-- |
-- | With an OK predicate `(<= 5)`, list `[0..9]` can be seen as:
-- |
-- | > [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
-- | > <--------------> <-------->
-- | > ok ng
-- |
-- | In this case `bsearchMain` returns the `(ok, ng)` = `(5, 6)` pair:
-- |
-- | > > let xs = [0..9] in do
-- | > > print $ bsearchMain (0, 9) (\i -> xs !! i <= 5)
-- | > (5, 6)
-- |
-- | Note that the closure CANNOT BE an exact match. Use a range-based predicate instead.
-- |
-- | Errors in edge cases
-- | --------------------
-- |
-- | While this function works for the above example, be warned that it's incomplete.
-- | It makes errors in certain edge cases:
-- |
-- | 1. The only `ok` item is at the end of the list.
-- | 2. The only `ng` item is at the beginning of the list.
-- | 3. There's no `ok` item or there's no `ng` item.
-- |
-- | So this function is wrapped by `bsearch`.
bsearchMain :: (Int, Int) -> (Int -> Bool) -> (Int, Int)
bsearchMain (ok, ng) isOk
| abs (ok - ng) == 1 = (ok, ng)
| isOk m = bsearchMain (m, ng) isOk
| otherwise = bsearchMain (ok, m) isOk
where
m = (ok + ng) `div` 2
-- | Binary search for inclusive range (from left to right only)
bsearch :: (Int, Int) -> (Int -> Bool) -> (Maybe Int, Maybe Int)
bsearch (low, top) isOk = bimap wrap wrap result
where
result = bsearchMain (low - 1, top + 1) isOk'
isOk' :: Int -> Bool
isOk' x
| x == low - 1 = True
| x == top + 1 = False
| otherwise = isOk x
wrap :: Int -> Maybe Int
wrap x
| x == low - 1 || x == top + 1 = Nothing
| otherwise = Just x
Union-Find [DONE]
- Union by rank or union by size
- 経路圧縮 (path compression)
ST array の場合:
データ構造
List [DONE]
- sort, sortBy
- group, groupBy
- cycle を使った uninterleave
let dys = [a | (a, True) <- zip ds $ cycle [True, False]]
in let dxs = [a | (a, True) <- zip ds $ cycle [False, True]]
in
- nub で非ソート済みリストを deduplicate する
- ソート済みリストの deduplicateion = 圧縮:
compress [] = []
compress (x:xs) = x : (compress $ dropWhile (== x) xs)
bytestring vs text [DONE]
- Haskell の char は 40 バイトらしい
- bytestring をマルチバイト文字に使おうとすると罠が色々ある
- このバージョンの text は内部データを UTF-16 でエンコードしている
最新の text
(AtCoder では利用できない) が Rust の String
に近い? まあ bytestring でいっか……
array [WIP]
- TODO: 内部のデータ構造は?
-
!
演算子でe
を取り出せるが対応のi
が無ければ死亡する (optional が欲しければ 2 分探索しよう?)- TODO:
!
演算子の計算量はO(1)
と思って良い?
- TODO:
-
assocs
で[(i, e)]
を取り出すことができる。 map や scan する場合はこれ? でも内部的にはリストではないはずか…… - accumArray の使い方
TODO: 2 次元配列の使い道
containers
IntMap [WIP]
2 分探索木と思えば良い?
IntSet
vector [Done]
MVector
含め使えるようになってきた。
vector-algorithms [TODO]
MVector のアルゴリズム一覧で、たとえば in-place なソートを提供するみたい。
通常は標準入力を読む際に VU.fromList . mapAndSortList <$> readStdinAsIntList
と書くだけで済む気がする。 Fusion のおかげで負荷も少ないはず……
モナド
IO / ST
というか Vector
の内部実装が気になります。
RealWorld?
D 問題メモ
重い。。
IntMap (key / value), IntSet (key のみ)
辞書は計算量やメモリ使用量の削減に役立ちます。
ABC 274 D
全探索では
YouTubeのvideoIDが不正です
つまり Vector
を使うと TLE だが IntSet
を使えば AC! しばらく理解できなかったし頭良いなと思いました。集合を使えば空間の大きさまで計算量を落とす事ができる時もある。なるほどなぁ……
点をオフセットで表現すると、単純な DP (空間配列のダブルバッファ) よりもシンプルな解答になって Haskell には易しいです。これも頭いいなぁ:
ABC 275 D
フィボナッチ関数よろしくメモ化するのが簡単そうです。 Vector
で出すと RE (runtime error) になりました。手元で大きな N を入力として与えると、デカい Vector を作った時点で heap overflow が発生します。
Atcoder のメモリ制限は 1GB (
IntMap を使えば 解決します 。ただし IntMap
は immutable なので、返値で IntMap
を返します。
IORef
に関して、 この辺を読む限り 参照先を変えられるポインタに過ぎないようです。IORef
に参照される値は immutable なので、全然手続型ではないな……?
Union-Find
ABC 259 D
TODO
雑多メモ
Write Yourself a Scheme in 48 Hours を軽くやってみる (repo)
Text
-
記事中では
String
を使っているが、 Haskell のString
は非常に効率が悪いことで有名だった。- UTF-8 を扱えるライブラリとしては
Text
が推されている。最近はText
の内部実装にも UTF-8 を使っているらしいが、パース中は ASCII 文字にしか興味がない。bytestring
を使ってみたい。 -
bytestring
で UTF-8 を扱う場合に罠があるという。 Octets が失われる? うーむ。。Text
はText
で面倒くさいけれどもText
にしておこうか。
- UTF-8 を扱えるライブラリとしては
-
Text
における 1 文字はT.singleton
で良い? 恐ろしく面倒くさい上に自信を失う。所詮 Rust しか使えないミジンコなんだ…… → 1 文字はChar
。内部実装がよく分からない (Rust の String と思っていいのだろうか) -
Text を使ったリポジトリ を見つけたけれど
unpack
してString
に変換している。
どうも Tex.ParserCombinator.Parsec
ではなく Text.Parsec
と Text.Parsec.Text
を import すると普通に動いた。 Text
も単なる Char
のストリームと見做せる気がする。このチュートリアルは古いのね……
Haskell
- サブモジュールは import できない?
GHC.IO
を qualified import してもIO.Encoding
の形でアクセスできなかった。直接GHC.IO.Encoding
を import しなければならない。これは Odin と同じで、僕が Odin を止めた理由でもあった……。 Public / private を export で表現する点も苦手で、理想の関数型言語が Haskell 以外で現れてほしい気持ちがある。名前空間もグローバルだしな。今もどこかでポスト Rust の関数型言語が開発されているのだろうか。 - Haddock でドキュメント生成。重い。構文は reStructuredText みたい。
- こうしてみると GHC のエラー出力は Rust に似ている (Rust が似ている?)
- 言語拡張 (LANGUAGE pragma) はファイル毎に有効にするか、 Stack なら
default-extensions
を書いてプロジェクト全体で有効にできる。 - ポスト GHCup の時代に Stack を使うのは止めようという話をちらほら見る。 Stack は GHC のインストーラとして使われていた……?
cabal
(CLI) には GHC のバージョンを切り替える機能もあるらしいので、今年の Advent Calendar 記事を参考に乗り換えたい。 - Nix に基づく開発環境も解説が欲しい。
Web 記事巡回
赤黒木とはノードに関連づけた『色』を利用してバランスされたソート済み二分探索木。これくらいサクッと書けたらよいのだけれど
Scala では本格的にモナドが使える。 Extensible effects ら辺が分からなかった…… (けどイメージは持てた)
Monad は基本的な表現を持った型クラスに過ぎない
Monad が満たすべき性質をシュッとしたコードを書くための性質だと思って見てみる
カリー化には多変数関数をバラすものとタプルをバラすものがある。二変数関数と関数閉包で多変数関数を表現できて嬉しい話しか知らなかった。
AtCoder ブラウザ拡張
ユーザースクリプト (grease) は Firefox でも動きました。問題の diff やユーザのレートを表示する拡張が良いです。ただ痒い所に手が届くものは Chrome 拡張も多かったです。
特に Haskell のハイライトを直すやつ:
灰 diff の C 問題が解けない (ABC 276)
つらすぎる。。 Haskell でバグり出すと止まりません。実装の方針が良くないのでしょう。
アルゴリズムのカバー率ではない部分で死んでおり、鉄則本を進めても案外レートは上がらないかもしれません。その方がある意味気は楽ですが。
- ZVON? にはコードの用例が載っていて良かった (たとえば accumArray)
- シグネチャはコードアクション (LSP) で出すこともできる
Union-Find の実装
Union-Find 木の内部データに Data.Vector.Unboxed.Mutable.MVector
を使う解答 を見ました。いい!
計算量削減
元コードで union by rank (size?) と経路圧縮が行われており、大変参考になりました。アルゴ式に解説があります。
もう少し型を頑張ってみたい
Unbox
を実装……できない
Int
の代わりに data UfNode = Child Int | Root Int
を使いたかったのですが、以下のエラーが出ました:
-- | * `Child parent`
-- | * `Root size`
- data UfNode = Child Int | Root Int
• No instance for (VUM.Unbox UfNode)
arising from a use of ‘VUM.read’
• In a stmt of a 'do' block: node <- VUM.read vec i
In the expression:
do node <- VUM.read vec i <略>
UfNode
が Unbox
ではないと。これには Haskell High Performance Programming を持ってきて対抗します。富豪プレイは最高だぜ (Haskell 本を 5 冊持っている顔):
- data UfNode = Child Int | Root Int
+ data UfNode = Child {-# UNPACK #-} !Int | Root {-# UNPACK #-} !Int
あれコンパイル通らない……? 大量の boiplerplate が必要なようですね
しかも代数的データの場合は載っていない。 Deriving 用クレートの template Haskell 展開結果を見ればいいのですが、もう boxed な MVector
使っちゃおっか……
IO モナドで実装
まずは IO
モナドで実装してみました。型パラメータが減って簡単です。
newtype UnionFind = UnionFind (VM.IOVector UfNode)
data UfNode = Child {-# UNPACK #-} !Int | Root {-# UNPACK #-} !Int
{-# INLINE root #-}
root :: UnionFind -> Int -> m Int
root uf@(UnionFind vec) i = do
-- ~~~
PrimState で実装
IO モナドと ST モナドを抽象する primitive
パケージの PrimMonad
及び PrimState
に移行しました。
newtype UnionFind s = UnionFind (VM.MVector s UfNode)
type IOUnionFind = UnionFind RealWorld
type STUnionFind s = UnionFind s
root :: (PrimMonad m) => UnionFind (PrimState m) -> Int -> m Int
root uf@(UnionFind vec) i = do
-- ~~
-
do
ブロックの中でRoot s <- VM.read vec py
のようにパタンマッチするとCould not deduce (MonadFail m)
というエラーが出ました。代わりにunwrapRoot
を使ってみました。 -
PrimMonad m => ..
が出る場合はINLINE
プラグマを付けておくのが無難らしいです。
Union-Find (Int 限定)
-- | Union-find implementation (originally by `@pel`)
newtype UnionFind s = UnionFind (VM.MVector s UfNode)
type IOUnionFind = UnionFind RealWorld
type STUnionFind s = UnionFind s
-- | `Child parent | Root size`. Not `Unbox` :(
data UfNode = Child {-# UNPACK #-} !Int | Root {-# UNPACK #-} !Int
-- | Creates a new Union-Find tree of the given size.
{-# INLINE newUF #-}
newUF :: (PrimMonad m) => Int -> m (UnionFind (PrimState m))
newUF n = UnionFind <$> VM.replicate n (Root 1)
-- | Returns the root node index.
{-# INLINE root #-}
root :: (PrimMonad m) => UnionFind (PrimState m) -> Int -> m Int
root uf@(UnionFind vec) i = do
node <- VM.read vec i
case node of
Root _ -> return i
Child p -> do
r <- root uf p
-- NOTE(perf): path compression (move the queried node to just under the root, recursivelly)
VM.write vec i (Child r)
return r
-- | Checks if the two nodes are under the same root.
{-# INLINE same #-}
same :: (PrimMonad m) => UnionFind (PrimState m) -> Int -> Int -> m Bool
same uf x y = liftM2 (==) (root uf x) (root uf y)
-- | Just an internal helper.
unwrapRoot :: UfNode -> Int
unwrapRoot (Root s) = s
unwrapRoot (Child _) = undefined
-- | Unites two nodes.
{-# INLINE unite #-}
unite :: (PrimMonad m) => UnionFind (PrimState m) -> Int -> Int -> m ()
unite uf@(UnionFind vec) x y = do
px <- root uf x
py <- root uf y
when (px /= py) $ do
sx <- unwrapRoot <$> VM.read vec px
sy <- unwrapRoot <$> VM.read vec py
-- NOTE(perf): union by rank (choose smaller one for root)
let (par, chld) = if sx < sy then (px, py) else (py, px)
VM.write vec chld (Child par)
VM.write vec par (Root (sx + sy))
-- | Returns the size of the root node, starting with `1`.
{-# INLINE size #-}
size :: (PrimMonad m) => UnionFind (PrimState m) -> Int -> m Int
size uf@(UnionFind vec) x = do
px <- root uf x
s <- unwrapRoot <$> VM.read vec px
return s
型ファミリー (型族) って何だろう
また謎が増えました。 Haskell 難しい……
TLE だと…… (277)
しかも解答の筋は別に間違っていないだと……。茶色にすらなれる気がしない (・ω・)
→ IntMap の更新ミスってるよ〜
ただデバフが無くても D 問題が解けないレベルと思うので、アルゴリズムをメインでやっていくのが良い気がします。
- IntSet でソートと重複除去ができるか
- compress = group . sort じゃん
セグメント木の実装
Inline module が欲しい
現在の Haskell には inline module が無いようです。Module.function
と名前空間を区切ることができません。
ScopedTypeVariables
こちら forall a m.
が無ければコンパイルエラーとなります:
queryByRange :: forall a m. (VU.Unbox a, PrimMonad m) => MSegmentTree a (PrimState m) -> (Int, Int) -> m a
queryByRange (MSegmentTree !f !vec) (!lo, !hi) = fromJust <$> loop 0 (0, initialHi)
where
!initialHi = (VUM.length vec) `div` 2 - 1
loop :: Int -> (Int, Int) -> m (Maybe a)
..
forall a m.
が無い場合、 queryByRange
の a
, m
と loop
の a
, m
が別物として扱われ、 a
と a1
の不一致、 m
と m1
の不一致が起こります。
激しいバグ
デバッグの仕方が分からない……。始めは IO
で実装すれば print
デバッグができて良いと思います。
MaybeT
を使うべき?
TODO: TODO: freeze したい
MVector
は Show
できません。 MShow
みたいなのものは std に無い気がしますし、 vector
の generic モジュールを参考に freeze したり、より汎用的な関数を作る必要を感じます。
散らかって来たので閉じます〜