茶色目指して

レート 400 が遠い。。 鉄則本 や Haskell High Performance Programming を楽しみながらボチボチやります。

Haskell の気づきメモ

NPlusKPatterns は危ない

これは数値にマッチするパタンを (n + 1) のように書くことができる拡張です。 1-based index を 0-based index に変換するときなどに使用しました。しかし n が負の数になる時はエラーが発生します。

$ ghci -XNPlusKPatterns
Prelude> 

Prelude> let x = 1
Prelude> let (n + 1) = x
Prelude> n
0

Prelude> let x = 0
Prelude> let (n + 1) = x
Prelude> n
*** Exception: <interactive>:2:5-15: Non-exhaustive patterns in n+1

このように罠がある以上、多少冗長でも let や where を書こうと思いました。 詳細 (未確認)

2 次元の可変配列には vector よりも array の方が向いているかもしれない

2 次元の不変配列には V.Vector (VU.Vector Int) のようなものが利用できます。ダブルポインタの発生は懸念されますが、そこまでパフォーマンスに影響は出ません。また各行の長さが違っても良い点はメリットになる時もあります。

2 次元の mutable vector が欲しかったのですが、 VU.create が使えず困りました。 State thread の表現力は予想以上です。

Vector で 2 次元配列を扱うならば、 (1, 2) のような 2 次元の添字を 1 次元の添字に変換すれば良いと考えました。たとえばグリッドの横幅を w として、 index = x + y * w のような式が考えられます。

実は、このような添字の汎用的な表現が型クラス Ix であると気付くことができました。また array は Ix を中心としたパッケージであると理解できました。

2 次元配列の添字の使い方 (array / Ix)

たとえば row-major な行列のリストを array の中に保存するなら、 newListArray ((0, 0), ((h - 1, w - 1)) list で array を生成し、添字 (y, x) でアクセスします。添字を (row, column) と見れば、 2 次元の array は row-major な行列であるとも解釈できます。

$ ghci
Prelude> import Data.Ix
Prelude Data.Ix>

Prelude Data.Ix> index (0, 4) 2
2
Prelude Data.Ix> index (2, 6) 2
0

Prelude Data.Ix> index ((0, 0), (5, 5)) (0, 1)
1
Prelude Data.Ix> index ((0, 0), (5, 5)) (1, 0)
6
Prelude Data.Ix> index ((0, 0), (5, 5)) (5, 5)
36

遅延評価で DP ができるらしい？

https://mobile.twitter.com/naoya_ito/status/1590483420404383745

map f xs の引数順は関数合成で便利

F# ではパイプライン演算子？　が使用されますが、 Haskell では関数合成が好まれる気がします。 map のシグネチャにもそれは表れているなと改めて思いました。

漠然とした興味

手続き型 Haskell は汚くてしんどい、純粋な Haskell は思いつくのが難しい

いずれにせよ、 Haskell は読むのも書くのも難しいと思います。

モナドのランク？

失敗しないモナドや、箱より文脈に近いモナドなど、何らかの違いを感じます。 State なんかは値というよりも関数のモナドですし。

ABC ノート

面白い問題が多いと気づいてきました。

• ABC 274 D: (IntMap を使って) 重複を消去すれば、計算量を O(2^N) から空間サイズ程度まで削減できる。基本中の基本みたいな問題です (死亡) 。

• ABC 275 C: ある種の全探索で十分でした。つらい。。

• ABC 275 D: Sparse なメモを使います。 274 D の経験後なら解けるべきだった (死亡) 。

• ABC 277 C: DFS, union-find + 座標圧縮 (からの全探索) 、 sparse な union-find などの解答があります。良問な気がします (死亡) 。

• ABC 278 D: 配列のゼロクリアは O(N) もしくは O(log N) 程度みたいです。実は生成の replicate も O(N) みたい 。今回はゼロクリアを O(1) で実現するため、世代番号を使う必要がありました。無事死亡……。
  言語拡張 TupleSections により \x -> (x, 1) を (, 1) と略して書くことができます。 Vector をタプルにマップするときなどに使えますね。

• ABC 278 E: 考察で計算量を減らすことができず死亡。。あとタプルの unboxed array は作ることはできないので気をつけます。 これを Haskell で実装するのに 6 時間もかかったよ…… 。これが AtCoder を 実装 > 考察 に変えるハックです。

その他ネタになりそうな話題

レートは実力の対数のようなものらしい？

喩えだとは思いますが、もしも水色 (レート 1,200) を目指すなら今 (レート 400 弱) より約 10 倍強くなる必要があります。うーむ (普通にやっていたら無理では……？) 。

1 問解くとレートが 1 上がるという説もあり、逆に実力とは……？

AtCoder Problems を問題一覧にすると良かった

AtCoder Problems (使い方) では、コンテストを跨いだ問題一覧が見れます。解答状況も見えて、たとえば 僕の場合はこちら 。いずれレコメンド機能やバーチャルコンテストも利用する時が来るかもしれません。

流石に鉄則本には対応していないようですね。自分でカウントします。

レートのシミュレータ で目標のパフォーマンスが分かる

これで目標設定が可能に……？　とはいえパフォーマンス値に勘が働きませんし、問題の色を見れば良い気はします。問題の色 = その色の参加者の 50% が解けた問題……だったはずなので、目標のレートより少し下の問題を安定して解ければ良いはずです。まず茶色を目指すなら、灰色後半の問題が解ければ良いはず？

言語サーバが動いていない気がするんだけど！

HLS 1.5.1 だからだと思っていたけれど、さすがにフォーマットしかできない言語サーバが 1.5.1 なんて高いバージョンのわけもないよね……

HLS が動いてなかった

言語サーバは重要です。エラー表示したり、 変数の型を表示したり 、コードアクションで型ノーテーションを補完したり……。あまりの有用性に涙が溢れます。

今まで言語サーバ無しで Haskell を書いていたのはある意味凄くないですか？ (泣)

原因

現在のファイル構成は以下です。この状態で Emacs を起動すると、 LSP のプロジェクトルートが abc-hs になっていました:

abc-hs
├── abc-277
└── abc-278
    ├── a
    │   ├── Main.hs
    │   └── test-cases
    ├── b
    └── g

対処方法 (暫定)

abc-* 以下に .projectile ファイルを置きます (Emacs の場合) 。これで ahc-* が LSP の workspace フォルダになります。他のエディタの場合は……最悪 .git を作ります？

また abc-* 以下で package.yaml を作り、実行ファイルごとに executables を書いて gen-hie (implicit-hie) で hie.yaml を作ります (Stack を使っている場合) 。これ自動化できないの……？

何とかしたいこと

• プロジェクトごとに GHC や HLS のバージョンを設定したい
• package.yaml で 1 つ 1 つ実行ファイルを列挙する手間を省きたい　 (自動生成できる？ cabal だったら楽だったりする？)

interact を使った宣言的な解答

Haskell で鉄則本を解く Youtube が現れました。 第一問の解答 の時点で、目を見張るほど宣言的です。これはかっちょいい。

YouTubeのvideoIDが不正ですhttps://www.youtube.com/playlist?list=PLmilE0iwpTVuBPYT5ZRuVGaf_PXUofwDk

module Main where

main :: IO ()
main = interact (encode . solve . decode)
 
decode :: String -> [[Int]]
decode =  map (map read . words) . lines
 
encode :: [[Int]] -> String
encode = unlines . map (unwords . map show)

solve :: [[Int]] -> [[Int]]
solve dds = case dds of
    [n]:_ -> [[n * n]]

interact :: (String -> String) -> IO ()
interact :: (ByteString -> ByteString) -> IO ()
interact :: (Text -> Text) -> IO ()

main :: IO ()
main = BS.interact solve

solve :: BS.ByteString -> BS.ByteString
solve = ..

main :: IO ()
main = BS.interact solve

solve :: BS.ByteString -> IO BS.ByteString
solve = ..

direnv で Haskell 環境切り替え

AtCoder では GHC 8.8.3 / HLS 1.5.1 を使いますが、他のプロジェクトでは最新の Haskell を使いたいものです。 cabal で環境を変えるというのがあるそうですが、アドベントカレンダーで記事が出るなら自分から調べに行くのもなぁと思います。

代わりに direnv でプロジェクト毎に環境変数が切り替わるようにすれば、 Haskell の環境を切り替えられるかも？

インストール

direnv 公式サイト通りインストールして、シェルのフックを設定します。

$ curl -sfL https://direnv.net/install.sh | bash

~/.bashrc:

if command -v "direnv" > /dev/null ; then
    eval "$(direnv hook bash)"
fi

~/.config/fish/config.sh:

if command -sq direnv
    direnv hook fish | source
end

バージョン切り替え

$ direnv edit .
$ direnv allow

PATH_add ~/.ghcup/ghc/9.2.4/bin
PATH_add ~/.ghcup/hls/1.8.0.0/bin

~/d/h/rogue-hs ❯❯❯ which ghc
/Users/tbm/.ghcup/ghc/9.2.4/bin/ghc

~/d/h/rogue-hs ❯❯❯ cd ../
direnv: unloading

~/d/hs ❯❯❯ which ghc
/Users/tbm/.ghcup/bin/ghc
direnv: loading ~/dev/hs/rogue-hs/.envrc
direnv: export ~PATH ~XPC_SERVICE_NAME

~/d/h/rogue-hs ❯❯❯ which ghc
/Users/tbm/.ghcup/ghc/9.2.4/bin/ghc

これで動いた？

ビルドが長いのでまた明日〜

30 分後

完璧に動きました。バージョンの異なる GHC を使った 2 つのプロジェクトで同時にエディタを立ち上げることができます。やったぜ。

stack や cabal は特に切り替える必要がありませんでした。色々やりたいことはあるので遊んでいきます。

[印刷用問題文]

『問題』ページ下部のボタンをクリックして、 競プロ典型 90 問 や 競技プログラミングの鉄則　演習問題集 の PDF をゲット？！　iPad に入れておきます。

iPad よりも高いけれど Kindle Scribe が欲しい

典型 90 問の解答は Twitter にある他、 リポジトリ に画像がまとまっているのでこれも PDF にしました。プリンタがあれば印刷するのですが。

State モナドが分かってきたぞ！

State モナドで mapAccumL

mapAccumL は状態を持ちながら map する関数です:

#!/usr/bin/env stack

import Control.Monad.State
import Data.List

main :: IO ()
main = do
  print $ mapAccumL (\acc x -> (acc + x, x)) (0 :: Int) [1, 2, 3]
  -- (6, [1,2,3])

この関数は Traversable なデータ型にしか実行できませんから、 Vector には実行できません。ただし Vector にも mapM は存在するので、 mapM と State モナドを使って mapAccumL と同等な計算を作れば Vector に対しても実行できます。

State モナドと do 記法を使って、なんとか mapAccumL を実装できました:

#!/usr/bin/env stack

import Control.Monad.State
import Data.List
import Data.Tuple

myMapAccumL :: (Int -> Int -> (Int, Int)) -> Int -> [Int] -> (Int, [Int])
myMapAccumL f s0 xs =
  swap
    $ runState
      ( mapM
          ( \x -> do
              acc <- get
              let (acc', x') = f acc x
              put acc'
              return x'
          )
          xs
      )
      s0

main :: IO ()
main = do
  print $ mapAccumL (\acc x -> (acc + x, x)) (0 :: Int) [1, 2, 3]
  -- (6, [1,2,3])

  print $ myMapAccumL (\acc x -> (acc + x, x)) (0 :: Int) [1, 2, 3]
  -- (6, [1,2,3])

これの無名関数の部分が Int -> State (s -> (Int, s)) という型であることを考えると、 mapM は各要素を State に写し、移された State の入出力を連結するものであることが分かり:

#!/usr/bin/env stack

import Control.Monad.State
import Data.List

main :: IO ()
main = do
  print $ runState (mapM (\x -> state $ \acc -> (x, x + acc)) [1, 2, 3]) (0 :: Int)
  -- ([1,2,3], 6)

これでたとえば累積和の計算ができます:

  -- 数列 → 累積和
  print $ runState (mapM (\x -> state $ \acc -> (x + acc, x + acc)) [1, 2, 3]) (0 :: Int)
  -- ([1,3,6], 6)

  -- 累積和 → 数列
  print $ runState (mapM (\x -> state $ \last -> (x - last, x)) [1, 3, 6]) (0 :: Int)
  -- ([1, 2, 3], 6)

  -- evalState = fst . runState

Vector には mapAccumL を実行できませんが、 State モナドを使った mapAccumL は Vector 版の mapM を使って実行可能です。

必要だった知識・理解

• State は s -> (a, s) の wrapper
  • state で純粋関数を State にできる
  • runState で State に実引数を与えられる
• mapM の過程は [a] -> [m a] -> m [a] という変換のイメージで、 sequence . map という 2 段階に分けて考えると、それぞれの要素を State モナドに写し、それらの入出力を繋ぎ合わせて全体で 1 つの State モナドにするもの

なぜ混乱したのか

脳みそが弱いからとしか言いようが無い。。

• do 記法が記憶に焼き付いた
• State を単なる関数として考えることを忘れ、ブラックボックスとして扱おうとした
• そもそも fmap mapM が mod_poppo 氏のブログ記事 から与えられた発想であることを忘れ、その意味を考えていなかった

何とかコンパイルできるコードを作り、質問して state 関数を教えてもらったことが取っ掛かりになりました。誰も僕の脳みそをデバッグできない。。こういう馬鹿さはずば抜けている気がします。でも自力で脱出するように上手くリードしてもらえると、意外になんとかなりますね。

まあなんとかやっていきます。。

部分適用とポイントフリースタイル

Pointless style と揶揄されることもあるポイントフリースタイルですが、 無名関数を in-place で書いたり関数合成が続く場合には非常に良いと思えてきました。久しぶりに Rust を書くと .map(|x| ..) という形が無念です。

構文

• if は関数ではない (if' は Prelude にはない)
• `f` で関数を演算子として使うことができる
• 演算子の部分適用 (セクション) の (a `f`) と (`f` b) は区別される
• (op) で演算子を関数として使うことができる

Prelude

• id :: a -> a
• const :: a -> (b -> a)
• flip :: (a -> b -> c) -> (b -> a -> c)
• succ, pred
• curry, uncurry

Wiki より

• Point とは空間上の点 (値) のことであり、関数が適用される値のこと
• つまり pointfree とは引数を省いた表記法
• Haskell の構文を pointfree にしたり元に戻す関数がある (pl, unpl) 。これを使って 様々なポイントフリースタイルのコンビネータ が発見された。必ずしも人間が見つけたわけでは無いのか。
  • owl: ((.)$(.))
  • dot: ((.).(.))
  • swing: flip . (. flip id)
  • squish: f >>= a . b . c =<< g

. や $ を関数として使うのが分かりません。 owl はコードゴルフで見た気がする？　今読む気はしませんが、この辺も使いこなしていきたいところです。

Stack script を :load するには (→ stack repl を使う)

デバッグのため REPL から stack script の関数を呼びたいとします。

ghci から stack script を :load すると、コメントを無視してしまうため Stackage のパッケージが読めません。かわりに stack repl の起動時にプロジェクトを選びます。もしくは stack repl a/Main.hs のように読み込むファイルを指定します。

Stack script をやめよう

Stack script を使っていたモチベーションは、環境構築が楽だった (oj のテストコマンドを ./Main.hs にできた) ことでした。 package.yaml もちゃんと書くことにしましたし、普通に stack でビルド・実行した方が良い気がします。

さて stack build abc279:exe:a-exe を試してみましたが、 a, b, c .. とすべてコンパイルされてしまいます。実行ファイル 1 つだけコンパイルしたいのですが……。

TODO

関数適用と実引数の色が同じだ

意外と tree-sitter が仕事していない……？

Misc

再帰やリスト内包表記を使わなくなってきた

Vector には基本パタンマッチができませんし、大体 fold で片付いてしまいます。 fold なら他の言語でも再現が楽です。

Rust で fold したことはないかも。

計算が派生する場合 (DFS など) は再帰関数を書いています。ファイルツリーを下っていくときなども再帰になりそう。つまり単純なループは foldl で表現できるし、新たな入力を取り寄せるためには再帰が必要なのでしょう。

forM_ 内で print するか、文字列を作って print するか

後者の方が美しいです。パフォーマンス的には……？

IntMap は確かに State モナドと相性が良さそう

do 記法は各行をポイントフリースタイルに変えてしまうから、 State モナドの do 記法によって IntMap の受け渡しをポイントフリースタイルにするのは自然に見えました。パフォーマンスはどうでしょう。

https://gist.github.com/wuerges/d84f9df6fb57789e9ba9828ccdf66953

Stream って直に触れるのだろうか (あるいは Iterator はある？)

Rust なら xs.iter().chain(iter::once(x)) のようにチェインができます。同じことを Haskell でやるには？

fold に限っては fold step x xs `step` x' のように書けます。

茶色パフォ後半が出るようになってきたけれど

解ける問題数は 3 から増えていません。

提出速度

高速で解答できると、同じスコアの参加者の中で順位が上がるため、パフォーマンスも上がるというだけです。つまり Vimmer であるかが問われます (違う)

水色ライン

順位 1,000 でパフォーマンス 1,300 程度でした。 5 問完答で 30 分弱、この辺が水色到達のボーダーラインな気がします。

レーティングの上昇速度

現在のレーティングの倍のパフォーマンスを出しても、レーティングは 11/10 程度にしかなりませんでした。さっさと水色に到達するには、 6 問解くしかありません。無理では……？

緑色目指して

正しくは 4 完目指して。

• 動的計画法
• グラフ (DFS, BFS, 連結グラフでグループ分け)
• Mod 計算
• 素因数分解、最大公約数、最小公倍数など

遅延評価で動的計画法

ズルいけれども動きます。また再帰ケース部を let の中の関数や where 句の関数に分けるとより簡単です:

let dp =
      array (0, n) $
        (0, 1) : [(i, acc `rem` unit) | i <- [1 .. n], let acc = step i]
    step i
      | i >= l = dp ! (i - 1) + dp ! (i - l)
      | otherwise = dp ! (i - 1)

print $ dp ! n

茶色後半までは解けるようになった気がする

とはいえ問題を難しくすると太刀打ちできません。まだまだ閉塞感が強く、 ABC が趣味と言える日は遠いようです。

今までも同じことを繰り返して来たのかもしれない

新しい表記法であれやこれやを書き散らかすのは、英語も数学も物理も同じですね。

どこまで行くのか

あと何回脳みそで発芽したような感覚を味わえば、 4 問 5 問と ABC を解いていけるのか。あるいは ARC やらヒューリスティックコンテストに挑むことができるのか。どこまで行けるか分かりませんが、経過を面白く思っています。

まだしばらくは這いつくばって行くしかないと思います。案外一生そんなものかな……

ヒューリスティックの本が出るとか

ポチった！　有名な人みたいですが、誰の本なんだろう！

僕もビーム飛ばしてみたいですね。何のことかさっぱりですが……

https://www.amazon.co.jp/dp/4297133601/

fold で 2 次元の動的計画法

方針

動的計画法の肝は枝刈りだと思います。入力を 1 つずつ受け取って探索し、テーブル上の『重複』を削除することで計算量をテーブルサイズ程度に押さえます。

Tips

fold を scan に変えたら、テーブルとして print できます。また print する都合上、横列を次の列に写す関数を使って fold すると捉えます。

演習

• 鉄則 A 18. 部分和問題

  • テーブルの形: 横軸は可能な値の組 (Vector Bool もしくは IntSet), 縦軸は入力値
  • 重複の削除方法: bool 値への和にする

• 鉄則 A 19. ナップサック問題

  • テーブルの形: 横軸は可能な重さの組 (Vector Int), 縦軸は入力値
  • 重複の削除方法: より価値が大きい方を選ぶ

• 鉄則 A 20. 最長部分列 (連続性を問わない)

  • テーブルの形: 横軸は入力値、縦軸も入力値
  • 重複の削除方法: より長い方を選ぶ

感想

入力が 2 種類だと fold するのはなかなかキツいです。それにせっかく純粋な解答を作っても、 IO / ST を使った方が速いんだ〜〜

IO / ST を綺麗に書けるようにするのも重要かもしれません。 tabulate を IO / ST 用に書き換えてみようかな

IO / ST で 2D 動的計画法 (ナップサック問題)

tabulate の IO / ST 版を作ればいいじゃない！

パフォーマンス面の確認

• Array (AC) は UArray (AC) よりも遥かに悪い
  • メモリ: 83 MB → 597MB
  • 実行時間: 174 ms -> 2466 ms
• ループ部分を関数に切り分けると (つまり高階関数を使おうとすると？) さらにメモリ使用量が倍近くなる (MLE)
  • ※ この tabulateIO 関数はまだまだ改良が必要

Haskell でナップサック問題を解く場合は、むしろ fold が安牌という気がしますね……

非インテリの所業

tabulateST を作りたいのですが、色々ハマって質問しています。全然課金して質問したいのですが、いつまでも taker のままで良いのでしょうか……

意外と Haskell の限界に近いのかもしれない

STUArray 版が通る ようにしてもらいました！　やや無念は残り、

• 型引数 e を具体的な Int に置き換えています。
• ユーザ関数 (f) の型推論ができませんでした

毎回 runSTUArray とか forM (range bounds_) $ \i -> do .. とかを書く方が現実的な気がしてきました。 tabulateST を使う案は棄却します。

tabulateST では INLINE 化しても意味が無かった

なんでだろう……？

• 非 INLINE 版
• INLINE 版

メモ化で 2D 動的計画法 (ナップサック問題)

tabulate の Map 版を作ればいいじゃない！

Unboxed 版は当然 MLE

まず Map を使う と MLE 。 tabulateST より使い勝手は良いけれど……

IntMap ならギリギリ AC

あら意外……！　AC です 。メモリ使用量は STUArray 版と変わらず、実行速度は明らかに遅いという程度。 TLE の危機はありますが、低空飛行で実戦投入できそうです。

また IxMap は無いので IntMap を使うのは少し面倒です。 index bounds_ i のようにして IntMap の引数に変換します。

index を忘れるとコンパイルエラーになるので、そこまで問題ではありません。

ただ、メモを sparse にする意味は無い

パフォーマンス的にも tabulateST の劣化版なのだなぁ……。

HashMap (unordered-container) では TLE

Strict 版なので MLE は避けられましたが、 時間制限を超えました 。妥当なところですね。 IntMap が TLE にならなかった方が意外でした。

型クラス Ix が便利でいいなぁ

n 次元座標の表現はもちろん、区間の表現もできることを知りました。 Prelude は総洗いした方が良いかもしれない……

$ ghci
> import Data.Ix

index

(min, max) 区間における相対位置を返します:

> index ((1, 1), (2, 4)) (1, 1)
0
> index ((1, 1), (2, 4)) (1, 2)
1

Row-major な行列では、添字は (y, x), サイズは (h, w) のように書きます。

range

n 次元のイテレーションもお手のもの:

> range ((0, 0), (2, 4))
[(0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(1,1),(1,2),(1,3),(1,4),(2,0),(2,1),(2,2),(2,3),(2,4)]

inRange

Inclusive range 内にデータがあるかを判定:

> inRange (1, 5) 3
True
> inRange (1, 5) 5
True
> inRange (1, 5) 6
False

> rangeSize ((0, 0), (2, 2))
9

そう書けばいいのか

unless

モナディックアクション？ では if の代わりに when / unless を使うとスッキリします:

forM_ [1 .. (n - 1)] $ \i -> do
  v0 <- VUM.read vec i
  unless (v0 == -1) $ do
     VUM.modify vec (max (v0 + 100)) (x100 VU.! pred i)
     VUM.modify vec (max (v0 + 150)) (x150 VU.! pred i)

なぜ未だにこんなことを……

listArray @UArray

@ で部分的に型を書くと、全体を推論してくれる場合があります:

input <- concat <$> replicateM n getLineIntList
let mat = listArray @UArray ((0, 0), (m - 1, n - 1)) input
-- let mat = listArray @UArray ((0, 0), (m - 1, n - 1)) input :: UArray (Int, Int) Int

newArray でも同様に:

  explored <- newArray @IOUArray ((0, 0), (h - 1, w - 1)) False

ツイート

いろいろツールがあるみたい

• AtCoderTags
  投票によって問題を分類分けしてくれます。サイトの見た目からして非常に良さそうです。

• AtCoder Problems
  ABC の問題一覧 (diff 表示 + AC 状況) や統計など。助かっています。

• AC heatmap
  GitHub の芝のように AC 数を表示してくれます。

• AtCoder Type Checker
  同レートの人たちと比較して、回答速度で performance を稼いできたか、それとも AC 数で performance を稼いできたのかを確認できます。僕は残念ながら早解き型でした。

Sequence でキュー (FIFO)

https://www.stackage.org/haddock/lts-16.11/containers-0.6.2.1/Data-Sequence.html

https://xtech.nikkei.com/it/article/COLUMN/20090804/335093/

Heap で優先度付きキュー

https://www.stackage.org/haddock/lts-16.11/heaps-0.3.6.1/Data-Heap.html

https://zenn.dev/naoya_ito/articles/f05885f9e302ba

HashMap で文字列キーのマップ

たぶん containers の Map よりも高速？

https://www.stackage.org/haddock/lts-16.11/unordered-containers-0.2.10.0/Data-HashMap-Strict.html

グラフの連結成分や塗り分け(?) のテンプレートが欲しい

まず既存の API を把握したいです。

Data.Graph だと……！ (containers)

内部的には Array Int [Int] です。

• buildG でお手軽作成 (ただの accumArray)
• components で連結部分をまとめ上げ (これが便利……！)
• scc (+ 長さ 1 を削除) で閉路も手に入る (便利……！)

Node, Tree, Forest あたりが複雑なので、直接使用するのは避けようと思います。

UnionFind

• ルート一覧 (連結成分の個数)
  連結後、 root v == v となる頂点の数を数える

けんちょん本でグラフ問題をエアプ

動的計画法なんかはサッと流しつつ、グラフを本格的にやってくれますね。

https://bookclub.kodansha.co.jp/product?item=0000275430

単一始点最短経路問題

Dijkstra 法

エアプじゃないので省略します。昔の僕はヒープが無い環境でプログラミングをしていたので、 O(N^2) の方を実装していました。ヒープって良いですね。

ベルマン・フォード法

(N - 1) 回の状態発展 (そんな用語があるかは知りません) を実施！　負のループ (サイクル) が存在しなければ (N - 1) 回までの発展で必ず収束します。 N 回目の発展で状態変化が起きたかどうかで負のループがあるかを判定できます。

全点対間最短距離 (Floyd–Warshall 法)

DP で解いちゃう！

最小全域木問題 (Kruskal 法)

辺に対する貪欲法！　連結の状態は Union-Find で持てます。

ネットワークフロー

最小カット問題 (辺連結強度の問題)

• s-t カットの最小容量は辺素な s-t パスの最大本数と等しい
• 辺素な s-t パスの最大本数は、残余 グラフ ネットワークを考えて取得できる

最大流 (フロー) 問題

• 辺に重みがある場合の最小カット問題 (最大流最小カット問題)
• 同様に残余 グラフ ネットワークを考えて計算できる (Ford-Folkerson 法)

なんとなく電流関連の定理 (テブナン？) と似ている気がします。一旦イメージだけ暗記してしまうか

2 部マッチング

始点と終点を追加して最大流問題に帰結！

点連結度

各頂点を 2 分割すれば辺連結強度に関する問題 (よく分からぬ)

プロジェクト選択問題

始点と終点を追加して、制約を重み無限の辺で表現する

積んでいる本

これを読んでおけば良かったなと今思います。 Robert Nystrom もグラフ理論はめちゃめちゃ使ったと言っていましたし。次はこの本か Haskell in Depth か Richard Bird か、それとも章末問題を解いてエアプ卒業か……

https://www.morikita.co.jp/books/mid/085281

tempel でスニペット挿入 (Emacs)

例

たとえば tr C-j で !_ = traceShow () () を挿入できます。通常の補完と名前空間が分かれているのが良いですね:

haskell-mode
(traceShow "!_ = traceShow (" (p "") ") ()")

今後は典型的なコードはテンプレートファイルにメモしていこうと思います。

その他便利そうなもの

(yn "if " (p "result") " then \"Yes\" else \"No\"")

(graphGen "input <- concatMap (\\[a, b] -> [(a, b), (b, a)]) <$> replicateM nEdges getLineIntList" n>
          "let graph = accumArray @Array (flip (:)) [] (1, nVerts) input" n>)

(fold "let result = foldl' step s0 " (p "input") n>
      "    s0 = " (p "_") n>
      "    step = " (p "_"))

(for2 "forM_ [0 .. h - 1] $ \\y -> do" n>
        "forM_ [0 .. w - 1] $ \\x -> do" n>)

(runSTUArray "let dp = runSTArray $ do" n>
        "arr <- newArray ((0, 0), (h - 1, w - 1)) (0 :: Int)" n>
        "      return arr")

(VU.create "let dp = VU.create $ do" n>
        "vec <- VUM.replicate (h * w) (0 :: Int)" n>
        "      return vec")

個別のケースをコードに書きつけても良い

一般解でなくても AC できれば良いのですし、むしろ境界を考慮したコードが書けて良いかもしれません:

main :: IO ()
main = do
  [n, k] <- getLineIntList
  print $ solve n k

modulo :: Int
modulo = 10 ^ 9 + 7

solve :: Int -> Int -> Int
solve 1 1 = 1
solve 1 k = k
solve 2 k = k * (k - 1) `rem` modulo
solve 3 k = k * (k - 1) * (k - 2) `rem` modulo
solve n k = _

Language Update 2023

vector が更新されると Unbox が簡単に導出できるようになるらしいので、それだけで満足な気がします。

螺旋本を買ったぞ！

先日のセールで『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』が Kindle 版 500 円になっていました。もちろん購入したので、 Kindle Scribe (*1) で読んでエアプしていきますよ〜〜

この本の評判としては、意外と競プロ (プロコン) に特化していないとのことです。たとえばソートの内部実装もやってくれます。娯楽としてはちょうど良いと思います。

(*1): マウントポイント

https://book.mynavi.jp/ec/products/detail/id=35408

小ネタ集

• IM.fromListWith (+) で sparse な accumArray ができる
  • fromList だと重複した要素が消えるため要注意
  • elems や keys は ascending order (昇順) がデフォルト
  • IM.toAscList, IM.toDescList は共に O(N)

Lang Update 2023 に備えて

追加予定のパッケージを見ていきます。

Misc

ありがとう有数の識者たち…… 🙏 普段の ABC 参加者は 10 人くらいですし、最新のハイパフォーマンス Haskell に詳しい人はさらに限られます 🙏 🙏ましてアップデートに注力してリサーチしてくれる人は 🙏🙏 🙏

ABC では通れば良いので、高速化ライブラリはヒューリスティックとかハイレート勢向け向けの気がします。しかし提出結果を比較して最適化の効果を実感できるので、趣味のためにもこうしたライブラリはガンガン入れてほしいです。

パッケージ

Hackage と Stackage の違いが分からないことに愕然としました。

• attoparsec
  速い parsec?
• bitvec
  めちゃくちゃ速い Bool の vector!
• deepseq
  seq や bang pattern と違って、データコンストラクタなどの内側まで評価してくれるようです。真に strict な評価が来た？！
• exceptions
  実行時エラー表示をマシにできるかも？ https://qiita.com/aiya000/items/6700753df2dfb9ae942e
• extra
  準 Prelude 気分。 Data.Tuple.Extra が特に良さそう です。 both とは Bifunctor には無いやつやし、トリプレットへのアクセサはそもそも無いんよ
• fgl
  グラフのつえーライブラリらしい 。なぜ見逃していた……？
• integer-logarithms
  Int# が出てくる謎ライブラリ。スルーかなぁ
• lens
  構造体の部分的更新に使えるらしい？　僕が AtCoder で使うことは無さそうですが、 AtCoder 外の準 Prelude みたいなライブラリを見ることができるのは良いですね。
• linear-base
  線形型、ということは所有権を Haskell に持ってこられるのだろうか……？
• massive
  repa 代打？！
• mono-traversable
  fmap ならぬ omap, traverse ならぬ ofold? Monomorphic container というのは Vec<T> のような普通のコンテナと思いますが、そんな一般的に実装できるのだろうか…… 。要チェックですね。
• mutable-containers
  Mutable な Deque なんかがあるっぽい？！　鉄則本での純粋な解答を見直す機会になります。
• mwc-random
  乱数生成　ヒューリスティック向け？　topcoder みたいに撃墜システムもありませんしね
• parallel
  ヒューリスティック向け？
• parsec
• psqueues
  Pure priority search queues. よく分かりませんが heaps の代わりになるかもしれません。
• random
  乱数生成　ヒューリスティック向け？
• reflection
  なにがなんだか。。
• regex-tfda
  正規表現
• safe-exceptions
  推奨されている方のやつ！
• template-haskell
  噂のやり過ぎてしまうテンプレートシステムだ！
• tf-random
  乱数生成
• utility-ht
  ビットシフトの演算子とか、 Enum に対する Ix とか if' とか。 それほしいやつやん！

repa は 1 回も使うことなく消えたよ……

インフラ強化

• safe-exceptions でマナーの良いコードが書けそう

前からあるじゃん

• fgl, massive, mutable-containers, psqueues が要チェックです！
• mono-traversable も見てみたい。
• extra と utility-ht も良し！

最新 Prelude はまたの機会に

こちらも良いものが増えてそう！

本日の ABC は D~ 異様に難しいらしい

つまり分が悪い。早解きと ARC A を解いてみるしかないか〜〜

待って

ARC 序盤って水色頻発地帯ですね……。ヤマ張って EDCP を進めますか……？

新たなリソースが

これはエアプと復習にめちゃめちゃ良いぞ……！

https://mobile.twitter.com/recuraki/status/1611647410249535488

新しい本を買い増した

Richard Bird 先生が難し過ぎた。。鉄則本購入者のセンサーが働く限り、この本がとても良さそう！

https://www.amazon.co.jp/gp/product/B09X9VGG2Y/ref=ppx_yo_dt_b_d_asin_title_o00?ie=UTF8&psc=1

Dense で immutable な Union-Find を作ってみたい

Union-Find テンプレートの改良を図ります。

• VU.modify で immutable かつ in-place なデータ更新ができるはず！
• また vector-th-unbox で自作データ型を Unbox にしたいです。

Union-Find の immutable 実装

Mutable な関数をタプルを返す関数に置き換えます。 State モナドにしてもいいかもしれません

Unbox の自動導出

古い vector パッケージではUnbox の実装するのは至難の業です。解決方法としては、

1. unboxing-vector (sum type 不可)

Vector.Unboxed と Vector.Unboxed.Mutable を unboxing-vector パッケージのモジュールに置き換えます。 Unbox の代わりに Unboxable を使うことになるので、既存のコードも編集が必要です。

c.f. unboxing-vectorの紹介：newtypeフレンドリーなunboxed vector

ただし sum type に対しては Unboxable を実装できない ようです。今回は利用できません。

2. vector-th-unbox (sum type も可)

Template Haskell で Unbox 実装をコード生成します:

-- vector-th-unbox: https://www.stackage.org/lts-16.11/package/vector-th-unbox-0.2.1.7
import Data.Vector.Unboxed.Deriving (derivingUnbox)

newtype UnionFind = UnionFind (VU.Vector UFNode)

-- | `Child parent | Root size`. Not `Unbox` :(
data UFNode = UFChild {-# UNPACK #-} !Int | UFRoot {-# UNPACK #-} !Int

_ufrepr1 :: UFNode -> (Bool, Int)
_ufrepr1 (UFChild x) = (True, x)
_ufrepr1 (UFRoot x) = (False, x)

_ufrepr2 :: (Bool, Int) -> UFNode
_ufrepr2 (True, x) = UFChild x
_ufrepr2 (False, x) = UFRoot x

derivingUnbox "UFNode" [t|UFNode -> (Bool, Int)|] [|_ufrepr1|] [|_ufrepr2|]

Sum type に対しても問題なく実装できています。

謎のパースエラーが出たので関数を分けています。

結果

UV.modify は遅い。全然 in-place に動いてない気がしますね:

また既設の Union-Find は Unbox 実装で倍以上高速になりました。今回は明らかなミスの修正でしたが、競プロにも盆栽の余地がありますね。だから黒魔術に走る人がいるわけですか (あの方 C++ よりも速いんだもん……) 。

レートが横ばいだ

今日 80 分かかった 4 問を 20 分で解けるようになるとは思えません。やはり 1,000 問解いて E まで解けないとダメか……！

Haskell 界で A 問題最速だ

下っ端は任せろ！

人のコードも読んでみようかな

Haskeller のコードは参考にならないことが多いです。

• リストを使っている。技巧的で難しいです。
• 普通の Haskell. 普通に難しいです (絶望)
• 黒魔術である。 C++よりも速いし当然読めないのである。

ただ今より良いコードを書こうと思えば、他人から吸収するしかないので、そろそろコードリーディングの下地を作って行こうと思います。思うだけかも……。

Haskell の話

こういう話はあと 10 本ぐらい聞きたい……！

https://podcasts.apple.com/jp/podcast/misreading-chat/id1364330509?i=1000496280601

こっちも……！

https://rebuild.fm/352/

こういうやつも……！

https://podcasts.apple.com/jp/podcast/episode-13-john-wiegley-on-categories-and-compilers/id694047404?i=1000385334618

そういえば動画派もいる

ライブコーディングという手もあったか……！　しっかりついていく必要があるので、あまり観ることはないのですが、勉強にはなるので時間を割くべくかもですがうーむ

https://m.youtube.com/@sampouorg

https://zenn.dev/magurotuna/articles/d5621291b8da87

バーチャルコンテストだと……！

とりあえずこれに出る……！

https://mojacoder.app/users/Ajinoko/contests/Ajinoko_ASC ジャッジが Haskell 非対応だ！　参加登録してごめんなさい！

定期開催

競プロのコミュニティはあるのか無いのかよく分かりません。

• 20:00 ~ 20:30: ABC 過去問
  https://twitter.com/i/communities/1502662995817959432
  短過ぎてうーむ

• 朝の定期開催コンテストを探したいです

結局は

一人でやろうということに。

PAST 上級本を買ったぞ！

3 月末発売ということで楽しみにしています。

https://www.amazon.co.jp/アルゴリズム実技検定-公式テキスト［上級］～［エキスパート］編-Compass-Booksシリーズ-大槻兼資-ebook/dp/B0BV9WVTF8?crid=25GSS1S3FF0UA&keywords=アルゴリズム実技&qid=1676200145&s=books&sprefix=あるごりずむじつ,stripbooks,195&sr=1-2&linkCode=shr&tag=rust-twitter-22&language=ja_JP&ref_=as_li_ss_shr&creativeASIN=B0BV9WVTF8&camp=1207&creative=undefined&linkId=6e7b1dd718bd60586e99625dae13d675

Thunder 本も買ったぞ！

今週出ますね。かなり楽しみです。

https://www.amazon.co.jp/dp/4297133601/

ヒューリスティックは言語の実行速度が点数に直結するはず (?) なので、 Haskell は辛いんじゃないかと思います。ここはまさかの Common Lisp か……？　何か面白い言語を探したいですね

毎日 3 問解き続けた 3 か月目の自分に負けるんだろうな

今 AtCoder 9 か月目なのですが、 AC 数 227 を見てそんな計算ができました。身近な夢から叶えていこう

NixOS 環境構築　脱獄失敗編

あるいは nixpkgs に ghc883 が無い問題。。 ghc884 を使って回避を試みました。

いや

Template Haskell を使っているせいか、 ld にリンクできないというエラーが出ました。いろいろ辛いね……

https://github.com/haskell/haskell-language-server/issues/1841

HLS のバージョンを 1.5.1 から 1.8.0 に上げてみたいと思います。 ソース をGHC 8.8.4 をパスに入れた上で nix-shell -p zlib から ビルド して……。

できた

変数のリネームもできますし、こっちのほうがいいかも……！

ABC 290 (日曜開催) も半 ARC 仕様だ

すなわち早解き会……！

辞書順

ABC 276 C - Previous Permutation など

辞書順で何番目？

Chokudai Speed Run 001 - K

O(N^2) の解答しか思いつかないので保留……。セグ木でいっかぁ

辞書順で次の順列は？

具体例を見ると:

• 123 45 → 123 54
• 1 2543 → 1 3245

つまり後ろから見て単調増加が崩れた点以下を加工します。

辞書順で 1 つ前の順列は？

具体例を見ると:

• 543 21 → 543 *12
• 54 312 → 54 231

つまり後ろから見て単調減少が崩れた点以下を加工します。

加工のやり方

めちゃくちゃ頑張る。。

nextPermutation で prevPermutation を作る

Haskell にも Vector.Mutable.nextPermutation があります。逆向きに nextPermutation するには、 Ord の向きを替えてしまえば良いので、それぞれの桁を Down で包みます:

prevPermutationVec :: (Ord e, VG.Vector v e, VG.Vector v (Down e)) => v e -> v e
prevPermutationVec =
  VG.map (\case Down x -> x)
    . VG.modify
      ( \vec -> do
          _ <- VGM.nextPermutation vec
          return ()
      )
    . VG.map Down

なお const () <$> VUM.nextPermutation や VUM.nextPermutation >>= \_ -> return () とは書けません。 ST モナドのライフタイム制限は厳密……！ (この例は安全側なので通してほしいけれど)

GHC 8.8.4 + lts-16.31 + HLS 1.8.0.0 がいいかもしれない

GHC 8.8.3, lts-16.11 と大差無い環境で、しかし変数のリネームができる！

なにより nixpkgs に ghc884 があるので NixOS でも環境構築できるのがありがたいです。難しすぎだよこの OS ……

groupBy が思っていたのと違った

Data.List の groupBy

Prelude Data.List> groupBy (\a b -> a + 1 == b) [1, 2, 3, 4]
[[1,2],[3,4]]

リストの先頭の要素と次の入力を比較しています。リストの末尾の要素と比較してくれませんか！！、

https://stackoverflow.com/questions/1316365/haskell-surprising-behavior-of-groupby

== と同じ性質を前提とするみたいです。詳しく読んでいません。。

utility-ht

こちらの groupBy は隣接要素を比較するとか。完全にこれだと思っていました……

> Data.List.HT.groupBy (\a b -> a + 1 == b) [1, 2, 3, 4]
[[1,2,3,4]]

HT.groupBy という形で使っていこうかな。あるいは groupBy を使わないのが無難かもしれません。

そろそろ人のコードを読もう

ABC 290 D の提出 を読みます。

モチベーション

実行時間 41 ms ですって。 C++のどの提出よりも速いのです。バケモンだよ……！

冗談だろ、ハニー
Haskell は AtCoder で 2 番めに速い言語
我々がロブスターならば、彼はレックウザであると言わざるを得ない

冒頭

• まずは LANGUAGE pragma から。
  • フォーマッタが ormulu ではないようです。
  • CPP を定義して #define が有効になっています。
  • GHC.Exts に primitive 型があります。 Haskell では Int も boxing の対象になるらしいですからね……
• #include MachDeps.h
  • 今、何が起きた……？

マクロ

1 行で INLINE プラグマ。まぁ #[inline]　に比べて {-# INLINE <name> #-} はセンス悪いですよね:

#define IL(f) {-# INLINE f #-}; f

入出力

ABC 290 D では以下の入力が与えられます:

3
4 2 1
4 2 2
4 2 3

パース部分。 rIntL, rIntL, rInt1L が Int のパーサで、それらの出力を liftA3 (,,) を使ってタプルにまとめています:

main = do
  t <- readLn
  qry <- getVecURest t $ liftA3 (,,) rIntL rIntL rInt1L

• readLn

rIntL, rInt1L

rIntL は Int を読み、 rInt1L は 1-based index な入力を 0-based な入力に変換します 。 Haskell では shadowing 非推奨なので超重要！　これなら NPlusKPatterns に依存せずにシュッと書けます。上手い:

IL(rIntL) :: StateT BSL.ByteString Maybe Int
rIntL = skipSpecialL $ StateT BSL.readInt

IL(rInt1L) :: StateT BSL.ByteString Maybe Int
rInt1L = subtract 1 <$> rIntL

TODO: なぜ StateT?

rIntL の L とは left かな？　実装を追います:

IL(skipSpecialL) :: (MonadState BSL.ByteString m) => m a -> m a
skipSpecialL = (dropSpecialL *>)

IL(dropSpecialL) :: (MonadState BSL.ByteString m) => m ()
dropSpecialL = modify $ BSLW.dropWhile (< ord8 '!')

-- import qualified Data.ByteString.Lazy as BSLW

• MonadState は get とか put のような State の基本的な API っぽいですね。ここ、すごい H 本で出てきた所だ！

TODO: 頑張って読む。

getVecURest

getVecURest は generic な実装に委譲しています:

-- import qualified Data.ByteString.Lazy.Char8 as BSL

IL(getVecURest) :: (VU.Unbox a) => Int -> StateT BSL.ByteString Maybe a -> IO (VU.Vector a)
getVecURest = getVecGRest

Generic な方の実装:

IL(getVecGRest) :: (VG.Vector v a) =>
  Int -> StateT BSL.ByteString Maybe a -> IO (v a)
getVecGRest n s = VG.unfoldrN n (runStateT s) <$> BSL.getContents

WIP

記事を書きました

Haskell for AtCoder な記事はこちらです。タイトルに比べて極めて個人的な内容なのがまずい気も……

• 環境構築編
• 失敗編

他に書きたいのは黒魔術編、ガバベンチ編、コード編です。また AtCoder に限らず、モナドやエフェクトにも興味があるので追々調べます。

小物

仮案

tuple2, tuple3 がかなり便利です。 uncurryした通常の関数に入力を丸ごと渡せることがあります:

getLineIntList :: IO [Int]
getLineIntList = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

tuple2 :: [Int] -> (Int, Int)
tuple2 [!a, !b] = (a, b)
tuple2 _ = error "not a two-item list"

tuple3 :: [Int] -> (Int, Int, Int)
tuple3 [!a, !b, !c] = (a, b, c)
tuple3 _ = error "not a three-item list"

getTuple2 :: IO (Int, Int)
getTuple2 = tuple2 <$> getLineIntList

getTuple3 :: IO (Int, Int, Int)
getTuple3 = tuple3 <$> getLineIntList

catPairs :: [(a, a)] -> [a]
catPairs [] = []
catPairs ((!x, !y) : xys) = x : y : catPairs xys

concatMap2 :: (a -> (b, b)) -> [a] -> [b]
concatMap2 f = catPairs . map f

また concatMap2 と extra パッケージがあれば、グラフ生成をポイントフリースタイルで書けます:

getGraph :: Int -> Int -> IO (Array Int [Int])
getGraph nVerts nEdges = accGraph . toInput <$> replicateM nEdges getLineIntList
  where
    accGraph = accumArray @Array (flip (:)) [] (1, nVerts)
    toInput = concatMap2 $ second swap . dupe . tuple2

重み付きグラフを格好良く書くのははちょっと厳しいかな……

入力処理の汎用性について

関数を分けるより、型クラスを作って getLine' @(Int, Int) みたいに書くほうが良い？

パースの方法 (空行区切り) も明示的に指定したくなってきますね。まぁ Int で空白区切り限定でも良いのではないでしょうか。

基本的な構文や言語機能に関し

合意できる点も増えたのでノートします。

• if, then, else
  キーワードが分かれているおかげで、それぞれの句で $ が使えます。

• Public item を module キーワードで定義する

  • Module キーワード以下は簡易 DB とみなし、エディタのコマンド経由で item を追加・削除すれば良いです。
  • Public item をソース上でハイライト表示すれば、 pub キーワードが無くても公開性を一目で見れます。

• 言語拡張が無いと弱い
  うーん

• INLINE, define, template haskell
  うーん

• モナドを合成すると重くなりがち
  うーん

• 所有権が無い、遅延評価を使う
  うーん。研究が進めば Haskell, Rust の次の言語が出てくれるのでしょうか。

黒魔術 Haskell からの植え替え・枝抜き

ShowBSB (ShowAsBuilder)

ByteString は普段入力にしか使っていないのですが、出力にも使いやすいように easy なコードを追加します。

まず ByteString な print 類に別名を与えます:

putBSB :: BSB.Builder -> IO ()
putBSB = BSB.hPutBuilder stdout

printBSB :: ShowBSB a => a -> IO ()
printBSB = putBSB . showBSB

そして ByteString.Builder への変換を共通のインターフェースで統一します

{-# LANGUAGE DefaultSignatures #-}

-- | Show as a bytestring builder
class ShowBSB a where
  showBSB :: a -> BSB.Builder
  default showBSB :: (Show a) => a -> BSB.Builder
  showBSB = BSB.string8 . show

instance ShowBSB Int where
  showBSB = BSB.intDec

instance ShowBSB Integer where
  showBSB = BSB.integerDec

instance ShowBSB Float where
  showBSB = BSB.floatDec

instance ShowBSB Double where
  showBSB = BSB.doubleDec

空行区切りで Vector を print する

WIP. 逐次 print vs ByteStringBuilder 一括出力？

WIP

永年初心者

$ 演算子の謎

コンパイルできない:

countCost v = costs VU.! v + sum $ map (costs VU.!) $ filter (`IS.notMember` visited) $ graph ! v

コンパイルできる:

countCost v = (costs VU.! v +) . sum $ map (costs VU.!) $ filter (`IS.notMember` visited) $ graph ! v

関数適用の優先度が最も高いならコンパイルできそうなものですが、 $ が絡むと謎が多い……

ループ処理

• (!! n) $ iterate step s0: n 回繰り返す
• foldl' step s0 input: 畳み込み / 入力処理
• until pred step s0: ループ / early return

foldl' と until の合わせ技が欲しい気もします。

追記

(!! n) $ iterate step s0 は 非常に低速で TLE になった ので止めましょう。

テーブルのサイズと DP の難度

2 要素のみ

fold で解けます。 DP という意識が湧きません。

N 要素のみ (ナップサック問題など)

fold で解けます。到達可能な範囲のみ更新するように気をつけます。そこそこ簡単な印象です。

N * N 要素 (最小共通部分列、区間 DP など)

途端に難しい。

N 要素 + N 要素 (最長増加部分列など)

相当難しい。

F 問題まで解けないと入水は厳しい

恐ろしい世界だ……年単位で時間をかけられるなら話は別ですが……

255 AC, 32 ABC 参加

フハハハハハハハハハ　こんなものか自分……！(・ω・)

剽窃

@ユーザ名 を付けてこれをパクろう:

https://zenn.dev/link/comments/1022553732563c

日報

Name shadowing は許可してしまうか

let visited' = IS.insert v visited とやった後に visited を使うことはありません。むしろ name shadowing を許可したほうがスコープが整理されて安全でしょう。やってしまいます:

  ghc-options:
    -Wno-name-shadowing

ただ思わぬ再帰で無限ループを作らないように気をつけます。

追記: let visited =IS.insert v visited の時点で無限ループになる……？ (悲しみ)

TODO: Stack script に警告抑制に相当するコメントを書き込む？

手続き型 Haskell が辛すぎる

1 問 6 時間かけて 謎に AC できない かろうじて AC するし、無残なコードがどうにもならない。そんなペースです。今、緑問題 streak 週間だから眠れないんだ……

Vec が無いのが辛すぎる

最大流問題の実装で苦しんでいます。 Vector は基本固定長配列なのです。 Capacity と lenght の区別も無いし……

頂点数を事前に数えて MVector を使うか、 IntSet や Sequence で誤魔化すか……。まずは [Int] IntSet で実装してから、後に盆栽します。剪定します？　それともパフォーマンスは追求しなくていいか……

foldM に early return が無いのが辛い

定石がほしい。。ガードで止めてますが、空回りが残るのは気になります、

forM に early return が無いのが辛すぎる

if の多重ネストになっています。 StateT で返値書き込みかなぁ

悩みどころは無限にあります。やはりハイレート Haskeller の盆栽的積み重ねがすごい……

AC した

天才！　まあ酷いコードなので、リファクタリングの手段を探したいと思います。いつ見つけられることやら……

それでも上手く行ったときのことを考えてしまう

時間ができた瞬間に都合の良い想像ばかりしてしまいます。何もかも上手くやり、理想的なプログラミングに近づいたとしたらと思うと、まだまだ離れる気にはなりません。 macOS も Git も Vim も Rust も Evil Emacs もそうやって習得してきたので、脳みそが変質するタイプの博打からは中々撤退できません。

マゾではないですが引き続きやっていきます。今のテーマは『Haskell で妥協の無い手続き型プログラミングがしたい』。今後は難問でこそ黒魔術的解法を調べてたいと思います。

テンプレートが 1,000 行を超えた

大半はコメントです。 AtCoder ではコード行数の下三桁しか表示しないことを確認しました (スマホの場合) 。

#include の検討

クソデカテンプレートはコンパイル時間にも悪そうです。特定の問題以外で使用しないコードは include して使うのが良いかもしれません。エディタ上で Import 類も削減できて良さそう……

• CPP と #include を使った Stack Script は動きます。
• HLS は CPP と #include を理解します。

#include を展開したい

stach ghc -- -E a/Main.hs の結果は gcc -E っぽいです。謎のコメントが含まれていてうーむ。。

これを動かしてみよう

./script extract problem/Template.hs の結果は #include が展開されている！　これなら AtCoder に提出できます。

https://github.com/mizunashi-mana/haskell-atcoder-template

gcc -E -P -w -xc -traditional

• -E: pre process の結果を吐く
• -xc: 標準出力に書き出し
• -P: 出力に linemarkers (# ..) を含めない
• -w: 警告を出さない

-traditional がよく分からないですが、入れておいたほうが良さそうです。

Linux で動かしましたが、リポジトリの作者が macOS ユーザのようなので (pbcopy を使っている) macOS でも動きそうです。

#include のみを展開したい

しかし #include <file-not-on-atcoder> 以外は GHC が理解できるので #include だけ展開したい。ツールを作るか……！

時間がある

すなわちエアプの時間が……！

2-3 finger tree

Haskell に特化した記事が Wikipedia にありました。 2 分木、 3 分木の亜種であり、ルートの位置を変えたり複数のルート持つことで、特定種別のアクセスに強くなる。内部実装は追えていないためエアプです。

https://ja.wikipedia.org/wiki/2-3_フィンガーツリー

3 分探索

2 分探索は単調増加する関数に対して有効です。 3 分探索は 2 次関数の極値などを見つけるために使えるようです。

問題によっては与えられた関数を紙の上で微分するだけで済みます

https://qiita.com/ganyariya/items/1553ff2bf8d6d7789127

なるほど。区間 [x_1, x_2] の中に極値があるとして、次の [x_1', x_2'] を作って 3 区間に分割すると、 4 点の大小を比較してどの区間内に極値があるのか分かると。

エアプだしこれだけでいっか……！ (完)

エアプのコツは

• 分かった気にならないこと (これは簡単のつもり)
• 分かった気になっていると思われないこと (これは難しい)
• 分かっていると思われないこと (これはこれで難しい)

massive でタプルを格納できる UArray ができそう

内部的には vector や primitive を使っている風ですね。これなら タプルもしまえるしスライスもできる ！　盆栽項目が増えてきた……！

TODO

生成・インデックス

• どの型クラス？　Manifest?

MArray の代わり

• write, read, modify, swap,
• new: ゼロ値初期化
• createArray?

runSTUarray の代わり

• createArrayST っぽい

Freeze / thaw

• unsafeFreeze が型クラスの中にある

コンテナを受け取る時は、必ず Bang Pattern を使おう？

Bang Pattern が効く瞬間を初めて見ました。これでスピードが倍になります。 Unbox ばりの高速化ですね:

-  let results = VU.create $ do
+  let !results = VU.create $ do
        !fw <- newFW_ABC286E (\v -> (1, values VU.! v)) nVerts edges
        runFW_ABC286E nVerts fw
        return fw

• ! なし: 1892ms
• ! あり: 962ms

{-# INLINE #-} は効くのだろうか

PrimMonad を使う関数は {-# INLINE #-} するべきのはずですが、今回は影響ありませんでした。

※ 高階関数も使っているので、複雑な状況ではあります

ST モナドの変換子が欲しい？

ST モナドの中にある 2 つの可変配列 (探索済み頂点と計算結果) を扱える文脈を作るには……？

TODO

Data.Graph の使い方が分からない

Forest, Tree / Node がメシー。。もう topSort 以外使いません。

Buffer のテンプレートがある

爆速 Haskller の方が push_back できる vector のようなデータ型 (Buffer) をお持ちでした。リサイズはできないようですが、一度アロケートしたサイズ内なら追加・削除ができる……！

速くて強い頭脳

このペース (リズム？) 参考になる……！　Haskell を含む各種言語でゴルフできるのも強い。。

https://www.youtube.com/watch?v=iv2PuoLmi-w

do で () を減らすことができる

便利なときがあるかも？:

-  input <- concat <$> replicateM 9 (map (== '#') <$> getLine)
+ input <- concat <$> replicateM 9 do map (== '#') <$> getLine

この例だと () を付けたほうが分かりやすいと思いますが、改行して延々と関数を作ることもできます。

リスト内包表記を List モナドで置き換え

リスト内包表記は builtin 構文 (のはず) なので、なんとなくズルをしている気分になります。一般的な do 記法に置き換えてみます。

コード

リスト内包表記:

  let !pos =
        [ [a, b]
          | a <- range bounds_,
            b <- range bounds_,
            a /= b
        ]

リストモナド:

   let !pos = do
        a <- range bounds_
        b <- range bounds_
        guard $ a /= b
        return [a, b]

guard の正体

Control.Monad#guard を見るに、 MonadPlus 上で定義されていますね:

Conditional failure of Alternative computations. Defined by

guard True  = pure ()
guard False = empty

上の例に戻ると、 do 記法の各行はポイントフリースタイルで書かれた関数であり、コード上に現れないリストを文脈のように受け渡ししています。その値が一度 empty ([]) になると、以降の >>=, >> は何もしなくなり、したがって guard 関数は early return を表現できる。ということだったはず。

動作上も early return にしてほしいですが、モナドに関しては実行モデルよりも表現するところを読み取る方が重要かと思います。某 Effects で実行モデルも妥協無い形になると良いのですが、きっとまだまだ研究中ですよね。

do 記法の desugaring

  let pos =
         range bounds_ >>=
           (\a -> range bounds_ >>=
           (\b -> (if a /= b then pure () else []) >>=
           (\_ -> return [a, b])))

pure () の部分が理解できません。文脈はリストではないのか……？　traceShow してみると、 a とか b はリストの中の単一の値を受け取っていますね。謎。。

あー >>= の中で concatMap している らしいです。 >>= をもう一段階 desugaring するべき ですね。モナド難しいよ！

IO モナドの empty

手続き型プログラミングでも early return 風の構文を、と思うと失敗します:

ghci> import Control.Applicative
ghci> empty :: IO ()
*** Exception: user error (mzero)

System.IO いわく:

Applicative IO
Takes the first non-throwing IO action's result. empty throws an exception.

MonadPlus IO
Takes the first non-throwing IO action's result. mzero throws an exception.

Applicative と Monad の関係を復習

Control.Monad を見るに、今の Haskell では Monad は Applicative の拡張として定義されています。 すごい H 本の説明は (未来予測していたとはいえ) 古い ということですね。

pure と return は同じ、 <*> と >>= の関係は以下:

m1 <*> m2

m1 >>= (\x1 -> m2 >>= (\x2 -> return (x1 x2)))

Applicative スタイルで書くとちょっとプロっぽい。

(a, b) -> ((a, b), (b, a))

dupe してしまう

ghci> import Data.Bifunctor
ghci> dupe x = (x, x)
ghci> swap (a, b) = (b, a)

ghci> second swap $ dupe (1, 2)
((1,2),(2,1))

Applicative スタイル

ghci> (,) <$> id <*> swap $ (1, 2)

こちらは汎用性が高く、入力の読み込みに使われている方もいますね:

(,) <$> int <*> int

自作の Union-Find を凍結可能にする

VU.create に相当する createUF 関数を作りたいと思います。

そういえば

読み出し中に木を書き換えないと高速化が望めないので、凍結はできませんでした。

昔解けなかった問題が解けるようになっている

実装能力と腕力向上のおかげです。特に既成ツールを使うだけで解ける問題はヌルっと AC できて良い感じです。 束の間ですが、 1 問 6 時間時代を突破して収穫の時間がやってきています。

当然今も解けない問題がある

6 時間コース、ですら終わらないか……！？　まあぼちぼち……

ラムダ式の引数で bang patterns

\(a) のように書くか、 \ の後にスペースを入れます (こっちが推奨かも):

let f1 = \(!x) -> 2 * x
    f2 = \ !x -> 2 * x
    g1 = \(!x) !y -> x + y
    g2 = \ !x !y -> x - y

IxIntMap, IxIntSet を作ってしまってもいいかもしれない

グラフの問題で boxing なデータ型を使用すると死にます。うまく次元を減らすべく考察するか、そもそも IntMap を Ix 越しのインターフェースで使うことで素直に解けるようになるはずです。

IxIntSet

作りかけていましたが、 Data.Ix に (i, i) -> Int -> i が無いので foldlIxIS を作れないことに気づいてしまいました。

また単ファイル内にモジュールを作れないため、関数名は *IxIS となっています。ちょっと使い勝手が悪すぎますね。 IxIS.* ならハイライトも良いのですが。。

さらに Ix では (Bool, Int) のようなキーに対応できないことは代わりありません。お蔵入りとします。

-- {{{ `IxIntSet`

-- | `IntSet` with `Ix` access
data IxIntSet i = IxIntSet (i, i) IS.IntSet

emptyIxIS :: Ix i => (i, i) -> IxIntSet i
emptyIxIS bounds_ = IxIntSet bounds_ IS.empty

fromListIxIS :: Ix i => (i, i) -> [i] -> IxIntSet i
fromListIxIS bounds_ is = IxIntSet bounds_ $ IS.fromList (map (index bounds_) is)

singletonIxIS :: Ix i => (i, i) -> i -> IxIntSet i
singletonIxIS bounds_ i = IxIntSet bounds_ (IS.singleton $ index bounds_ i)

insertIxIS :: Ix i => i -> IxIntSet i -> IxIntSet i
insertIxIS i (IxIntSet bounds_ is) = IxIntSet bounds_ $ IS.insert (index bounds_ i) is

deleteIxIS :: Ix i => i -> IxIntSet i -> IxIntSet i
deleteIxIS i (IxIntSet bounds_ is) = IxIntSet bounds_ $ IS.delete (index bounds_ i) is

memberIxIS :: Ix i => i -> IxIntSet i -> Bool
memberIxIS i (IxIntSet bounds_ is) = IS.member (index bounds_ i) is

notMemberIxIS :: Ix i => i -> IxIntSet i -> Bool
notMemberIxIS i (IxIntSet bounds_ is) = IS.notMember (index bounds_ i) is

nullIxIS :: Ix i => IxIntSet i -> Bool
nullIxIS (IxIntSet _ is) = IS.null is

sizeIxIS :: Ix i => IxIntSet i -> Int
sizeIxIS (IxIntSet _ is) = IS.size is

unionIxIS :: (Ix i, Ord i) => IxIntSet i -> IxIntSet i -> IxIntSet i
unionIxIS (IxIntSet bounds_ is1) (IxIntSet _ is2) = IxIntSet bounds_ (IS.union is1 is2)

intersectionIxIS :: (Ix i, Ord i) => IxIntSet i -> IxIntSet i -> IxIntSet i
intersectionIxIS (IxIntSet bounds_ is1) (IxIntSet _ is2) = IxIntSet bounds_ (IS.intersection is1 is2)

filterIxIS :: Ix i => (i -> Bool) -> IxIntSet i -> IxIntSet i
filterIxIS p (IxIntSet bounds_ is) = IxIntSet bounds_ (IS.filter p is)

-- foldlIxIS :: Ix i => (i -> a -> i) -> a -> IxIntSet i -> a

-- }}}