AtCoder で Option も Result も ? で .unwrap() する
競技プログラミングでの Rust のつらさのひとつに .unwrap() と9文字も書くのがだるいというのがあります。エラー伝搬は ? 1文字なのでエラー無視も楽に書きたいところですが、この記事にあるように stable Rust が入っている競プロサイトでは無理そうに見えます。ところが、実はできます。1
fn main() { main1().ok().unwrap() } fn main1() -> Result<(), Never> { // ここにメインの実装 dbg!("foo 42 bar".split_ascii_whitespace().nth(1)?.parse::<i32>()?); Ok(()) } enum Never {} impl<E: std::fmt::Debug> From<E> for Never { fn from(e: E) -> Self { panic!("unwrap ?: {:?}", e) } }
解説
現在の AtCoder 上の Rust はコンパイラのバージョンが 1.42.0 なので ? の仕様は (v2 になる前の) try_trait です。ここで Option に ? して Result を early-return するための型 std::option::NoneError は #[feature(try_trait)] がないと名指しできないのですが、 Debug トレイトを持つすべての型からの変換なら stable の範囲で書けるため、 From<NoneError> が実装できてしまいます。標準的に使われるエラーは std::error::Error トレイトなので Debug + Display 以上と分かっているし fn binary_search(&self, x: &T) -> Result<usize, usize>2 のように「エラー」ではない Result もだいたい Debug です。
ちなみに try_trait_v2 では専用の FromResidual トレイトを実装する必要がある3のでこういう抜け穴はありません。
main 関数に書きたい場合
fn main() -> Result<(), Never> { // ここにメインの実装 Ok(()) } #[derive(Debug)] enum Never {} impl<E: std::fmt::Debug + Clone> From<E> for Never { fn from(e: E) -> Self { panic!("unwrap ?: {:?}", e) } }
Never: Debug にするとそのまま main にできるのですが、 T: From<T> との重複実装が許されないため、変換できるエラー型を絞る必要があり、たとえば Debug + Clone を課すと良さそうです。 std::marker::PhantomPinned を用いて Never: Debug + !Unpin にして E: Debug + Unpin にできれば使い勝手良くなりそうですが、なぜかできませんでした (T: From<T> との重複判定が消えないため)。
-
.unwrap()を直接書く場合と比べるとエラー時に表示されるソースコード位置が変わってしまう問題はあります。RUST_BACKTRACE=1で1つ下を見ましょう。↩ -
partition_pointが 1.52.0 からなので AtCoder では仕方なく使ったりします。↩ -
try_trait_v2については以前の日記にも書きました。 https://toslunar.hatenablog.com/entry/2021/08/03/230856↩
Rust の Iterator で cumsum をどう書くべきか、あるいは map の闇
Rust の Iterator で cumsum をどう書くべきか、あるいは map の闇
最近、競プロ典型90問を解いて競プロのリハビリ兼 Rust 練習しています。
Iterator::scan の謎
cumulative sum といえば Haskell でいう scanl 0 (+) だと思っているので it.scan(0, |a, b| a + b) と書けば良いだろうと scan を見に行くと、予想に反する型がついている。型は少し省略して書くと
fn scan<St, B>( self, initial_state: St, f: impl FnMut(&mut St, Self::Item) -> Option<B>, ) -> impl Iterator<Item = B>
なのだが、 St と B が異なっていることからも分かるように 0 番目に initial_state を返す実装ではないのが残念だし、逆に長さを縮める機能を Option を返すことで実装しているのも意図が分からない。
つまり、後者の目的で scan を使うくらいなら map_while (since 1.57) で十分だし、 _while 要素もないので map (FnMut(Self::Item) -> B を渡す) で良く、 cumsum は
std::iter::once(0) .chain(it.map({ let mut s = 0; move |a| { s += a; s } }))
となる。
Iterator と FnMut
副作用のある関数を書いて良いのが盲点で、実際そういう言語だから map という名前で
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
あるいは mapM 相当だと思っておくのが自然だった。 Rust だと state monad 使う面倒さがなくて楽。めでたしめでたし。
とはいえ、 Fn/FnMut/FnOnce の区別みたいなところでも mut ref は unique ref という話みたいな対応もあって、 API 設計の意図が mut 側か unique 側かは分からない。副作用があっても実装が変わらないから FnMut とも言えるし、必要条件の側を考えて「同時に callback が呼ばれないから Fn を課す必要はなく、 Option::map などと違って 2 回以上呼ばれるかもしれないから FnOnce では足りない」という理由で FnMut になっているとも言える (これらは言い方が違うだけ)。
DoubleEndedIterator
Rust の Iterator のうち一部は後ろからも値を取り出せる (next_back)。たとえば、よく書くのは for i in (0..n).rev() だが、全部読んで Vec::reverse のような実装ではなく end -= 1 を返すような効率の良い実装が呼ばれる (std::ops::Range<A> については Iterator ならば DoubleEndedIterator)。
さて、 Iterator::map のドキュメントをよく見るともとの iterator が DoubleEndedIterator なら map 結果も DoubleEndedIterator を実装するらしい。見るからに副作用がやばい。そう思ってドキュメントを確認するともっと目立つところに具体例付きで注意書きがある。上の cumsum 実装も同じ理由で .rev() などすると壊れる。
.map(f).rev() は .rev().map(f) に直すように lint 出ても良いくらいだと思うが、 DoubleEndedIterator は 1 回 rev して終わりと限らず両端から自由な順序で取り出す想定の API だから pure function で map して DoubleEndedIterator を保ちたい用途がないとも言い切れない。
advanced_by
ところで、 for i in (0..n).step_by(k) は上限と modulo を指定できて便利なだけでなく O(n/k) 時間で動く。これは Iterator (required method は next のみ) は nth を自動実装しているが std::ops::Range が O(1) 時間の nth を与えることで実現されている。
自分で .map(f).rev() と書くことはないはずだが、 .map(f).step_by(k) は書きかねないので、 rev がやばいのなら step_by もやばいのではと思って調べたところ、これはセーフ。
Iterator::map が副作用無視の nth の高速化をしないことが保証されているか気になって iterator map nth で GitHub issue を検索したら advanced_by (unstable) の tracking issue の中で議論されていた。 map の副作用の注意書きすでにあるし nth でも副作用飛ばそうぜみたいな意見もあって一応予断を許さない雰囲気はちょっとある。競プロに限らなければ順序不定でもよい副作用とか消えても良い副作用とかいろいろあるので対立もやむなし。
立場をあえて明確にすれば自分は現状に賛成。 DoubleEndedIterator::rev は subtrait として分かれているから自己責任で、 Iterator::step_by が自動実装と挙動が違ったらやばすぎるみたいな裁定で正しいと思う。 Iterator::last は DoubleEndedIterator::next_back ではないし Iterator::count は ExactSizeIterator::len ではない。
AtCoder で cumsum したいとき
自分で書きたくないなら itertools_num::ItertoolsNum::cumsum か ndarray::ArrayBase::accumulate_axis_inplace を使えばよさそう。いずれも最初に 0 をつけたい場合はいじる必要あり。
cumsum を書く場合は map 後すぐ collect_vec() しておけば罠を踏むリスクはない。そもそも、ライブラリ整備せずその場で書くとなれば短いのが強く、
let mut s = vec![0]; // let n = a.len(); // 別のところで入力しているはず // s.reserve(n); // Rustでそんなにパフォーマンス気にせずともACとれるはず for i in 0..n { s.push(s[i] + a[i]); }
とするか、 i, n の typo を避けて
let mut s = vec![0]; for a in &a { s.push(s.last().unwrap() + a); }
にしそう。
try_trait_v2でOptionとResult両方に?を使う
この前 NoneError (try_trait (v1) の実装) が消えていたのを見て、どうやら try_trait_v2 に移行したらしいということで勉強した。
参考：RFC https://rust-lang.github.io/rfcs/3058-try-trait-v2.html
Result<T, E> の Ok(t) については t: T があれば良いが、 Err(e) については型情報を持ったまま return に処理を移すために e: E ではなく Err(e): Result<Infallible, E> を "residual" として残すことになるというのが v2 のポイント（v1のときに不勉強だったのに差分を説明……）。もちろん、この2通り（early-return しないかするか）は enum で表現され、なぜか Result::{Ok, Err} ではなく ControlFlow::{Continue, Break} が使われる。
Option, Result 両方を ? できる関数を書くには Option<Infallible>, Result<Infallible, E> について FromResidual を実装した型をつくる。コード例では OptionResult<T, E> としたが、 struct Foo(Option<Result<T, E>>) のようにもできるはず（いずれにせよ orphan rule により新しい型が必要だし、そもそも Option<_> や Result<_, _> はすでに impl Try されてしまっていて重複不可）。
#![feature(try_trait_v2, try_blocks)] // try_blocks は使用例のみで使う。 use std::{ convert::Infallible, ops::{ControlFlow, FromResidual, Try}, }; #[derive(Debug)] enum OptionResult<T, E> { Ok(T), Err(E), None, } impl<T, E> FromResidual<Option<Infallible>> for OptionResult<T, E> { fn from_residual(_: Option<Infallible>) -> Self { OptionResult::None } } impl<T, E, E0> FromResidual<Result<Infallible, E0>> for OptionResult<T, E> where E: From<E0>, { fn from_residual(e: Result<Infallible, E0>) -> Self { OptionResult::Err(e.unwrap_err().into()) } }
また、残念ながら、 -> OptionResult<T, E> な関数に ? を使っていくにはこの型自身の値も ? できる必要があることになっている。すなわち Try trait を以下のように実装する（使わないなら todo! で十分）。
impl<T, E> Try for OptionResult<T, E> { type Output = T; type Residual = OptionResult<Infallible, E>; fn from_output(t: T) -> Self { OptionResult::Ok(t) // ここも todo!() にしても良いが、 try block で便利 } fn branch(self) -> ControlFlow<Self::Residual, T> { todo!() } } impl<T, E> FromResidual<<Self as Try>::Residual> for OptionResult<T, E> { fn from_residual(_: <Self as Try>::Residual) -> Self { todo!() } }
なんでも Result<Option<T>, Box<dyn std::error::Error>> にするのが使い勝手良さそうということで、使用例は以下のとおり。
fn main() { let mut xs = "42,3,foo,7".split(','); for _ in 0..6 { println!("{:?}", f(&mut xs)); } } fn f<'a>( it: &mut impl Iterator<Item = &'a str>, ) -> Result<Option<i32>, Box<dyn std::error::Error>> { let res: OptionResult<_, _> = try { it.next()?.parse::<i32>()? + 1 }; res.into_result() } impl<T, E> OptionResult<T, E> { fn into_result(self) -> Result<Option<T>, E> { match self { Self::Ok(t) => Ok(Some(t)), Self::Err(e) => Err(e), Self::None => Ok(None), } } }
Ok(Some(43))
Ok(Some(4))
Err(ParseIntError { kind: InvalidDigit })
Ok(Some(8))
Ok(None)
Ok(None)
ICFPC 2021 振り返り
今回はおもに解の手動更新用のGUIを作っていた。入力をグラフとしてGraphvizで可視化するするのとかも初期はやっていた。
グラフ表示の位置などのヒント情報を用いてGUIの頂点に色を塗るとか、そこからGUIで動かす頂点選択するとかは時間内に思いつきたかったなあ。
今年は WebAssembly (wasm) がなかなか良い働きをしていて、Rust実装を使い回しやすくなったのは大きい。使いやすかったかというと微妙なところもなくはなく……。Rustから生成、TypeScriptで使うという2点に分けて以下に書いた。
いろいろ技術ごとに振り返ってみる。
Rust
wasmを準備したのは正解。 evcxr_jupyter を動かして Jupyter Notebook で動いて楽しいとか言っていたが、使わなかった。imosにRust用のファイル置いておくよう言われて開始前に cargo init および去年使ったマクロをサンプルとして置いたのは良かったと思う。
コンテスト中に書いた行数でいうと今年はそんなにRustを書いていないような気がする。
追加データで負の座標が出てきたのはx座標に2を加えて対処されたが、 serde_json::from_reader などと書くのが簡単すぎるせいで座標ずれバグをつぶしにくかった。型を分けるのは無理なので、ずらしたかの情報をstructに足して正気を保つようにした。
#[serde(skip_serializing_if = "Option::is_none")] #[serde(default)] pub internal: Option<InputInternal>,
他にも入力時に多角形の向きが直されていて、実は線分が多角形に含まれるかの判定にもその仮定が使われているみたいな罠もあり、ついでに気付くことができた。
iwiが普段エラー処理anyhow使っていると言っていたが、Unagiでも使っていくべきなのでは。
かつて、stderr軍拡競争はloggingで平和解決したはずだが、Rustになってloggingはどうなったんだっけ。
serde
神。毎回使うので使い方も慣れてきた。
今回のJSONはbonusのシリアライズ仕様がイケてなくて、
type Bonus = { bonus: string, problem: number, edge?: [number, number], }
みたいな仕様だったが、serdeのattrつけていけばなんとかなるはず。実際は BREAK_A_LEG 無視されたのでやってないが。
#[serde(rename_all = "camelCase")] struct { .. } #[serde(rename_all = "SCREAMING_SNAKE_CASE")] enum { .. }
なども使っていきたかったが、 WALLHACK を WallHack と誰かに書かれてしまった後なのでできず。
ordered-float
From<u8> がなくて困ったらしい。Haskellの Num は (+), (*), abs, signum, fromInteger, (negate | (-)) が良いかというと abs, signum は違う気がしてしまうので結局分からないが。
wasm-bindgen
Vecを #[wasm_bindgen] できないのはつらくて、serdeによる変換に頼ってしまったが、ドキュメントにはパフォーマンス悪いかもとかわざわざ書かれていて、無駄に不安になっていた。Rustから型をexportしなかったのでTypeScript側でも型を書き直している。
i64を変換するのも不安要素で、f64になるのかbigint的なのになるのかも知らないし。
Result<T, JsValue> を返す明示的なエラー処理をしなくてもrustでのpanicがjs側のエラーになるっぽいのは良かったが、巻き込んで落ちるのが直せなくてつらかった。原因はいまだ不明。
JavaScript / TypeScript
wasm関係続き
async import よく分からない。その場で調べたので準備不足。
webpackのWasmPackPlugin使ったほうが良かったか。結局make file書くのは不毛だが、wasm-pack buildするタイミングは自分で決めたいし、今回はwasm mime type問題で後処理も発生していた。
1ファイル(index.html + index.js くらい?)で済めば file:// で開いても動くからwebpackにしたのに、.wasmが別ファイルというのが罠。http-serverが.wasmを正しく扱わない（またmime type問題）のも問題。wasmがファイルの先頭から（読み込み完了する前に）ネイティブコードに？1-pathで変換する設計を昔聞いたときはよくできているなって思ったが、mime typeあってないとそのAPIが使えません（読み込み終わってからByteArray渡してね）って仕様になったのは納得できてない。
tosk.jpの置かれているValueServerが.wasmを正しいmime type返さない。設定をユーザーが変えられるのかみたいなことを知らない。この辺の一般知識がない。imosのいつものicfpcサイトではちゃんと動いたので多分Googleは偉い。github.ioとかにしても良いが、こういう非公開用途で困る。
PIXI.js
PIXI.jsの採用は迷惑掛けてしまった。WebGL直接は書きたくないのでjs側から書くには楽だが、Rustのライブラリ探しておくのが理想か。svgのpathくらい描画する機能あっても良いと思うんだけど……（無いことを知っていたのでなおさらなぜ選んだって感じだ）。
GUI、model matrixではなくview matrixをいじるべき場面なのに手動で線形変換の逆変換求めていたりして無駄だった。
というか、WebGLとsvgどちらで行くかの選択の問題もある。svgをインタラクティブなGUIに使えない気がしたが、sulumeがちゃんとしたのを作っていて感心した。
UI一般
色を適当に決めてしまったが、matplotlibからcolormaps拾ってくるくらいの準備はしておきたかった。具体的には、edge長の違反量に応じた色付けという要望が出ていたのに実装せずに終わってしまった。
index.html直書きで大丈夫だという予定だったが、React入れても良かったよなあ。npmはcargoほど安心して依存追加できない。でかいパッケージが相性問題起こしがちで、たとえばwebpackの設定を変えないといけなかったような。あまり良く分かっていなくて、npmをyarnにするみたいなのは平時に試しておいてもよかった（これが関係あるのかさえ分かっていない）。
他
package-lock.json で編集合戦が発生していたのは準備不足。自分とimosの環境では "lockfileVersion": 2 だがsulumeの環境では "lockfileVersion": 1 で他の場所にもdiffが出ていた。
自分もnodeのバージョンをコンテスト中に12から16に上げたので人のことを言えないが、こういうやばさはなかったと信じたい。
チーム開発
表記ゆれ (input/problem, output/solution/pose, score/dislike) がやばい。ソルバー班の考えやすい普段の言葉遣いでやっているが、poseも読み込むし、dislikeは最終的なチームスコアに変換される。「型の名前くらいは公式に従っておいて、変数名は自由」みたいなのが良いのかなあ。vscodeで型や変数のrenameするのは簡単だが、1回pushするとconflictをおそれて直せなくなって const solutionJson = this.pose; とか runCheckSolution1(input: Problem, output: Solution): void とか書き続けてしまった。
ソルバー側が負の座標や多角形の向きを気にすることなく開発できるのはあまりに大事なので、ソルバーからも手動からもvisualizeしたいという要求をどう処理するかということになりがち。今年はy座標が下向きなので平和だった。
cargo fmt してほしい。自分のファイルだけ rustfmt するのはちょっと面倒。同じファイルを同時編集する場合は、1ファイルよりさらに細かい単位のみを自動整形したくなるが、それが（たぶん）できなくて困る。
hard tabでインデントしたいならそれに合わせても自分は文句ないので、 rustfmt.toml 作るのが良いのでは。今気付いたが、空の rustfmt.toml を置きさえすれば個人の global config の適用回避できるっぽい……。実際に src/lib.rs で tab vs spaces の編集合戦を原因の一部とするmerge失敗があったので、実際に損している。 auto-mergeになったと聞いていたが検証したら自分のgitの設定では衝突したので、そちらに対策を入れるのが先という可能性もある。
iwiがgit submoduleを使わず直接足したのは正解だと思っていて、1回ライセンスを確認するほうが、後で誰かが操作失敗する可能性や、VSCodeのgitタブでsubmoduleの存在が表示されてうざいという認知負荷より安い。GitHubがメインの言語Javaって表示するのが気になって後で直したが。
「だから僕は音楽を辞めた」を聴いて思ったことを書いていく
1回しか聴いていないしMV見なかったけど140字におさまらない感想が出てきそうだったので。これは正当でない解釈や無関係の話題を出すための予防線だし，1回でそれなりに聴き取れているという主張でもある。ヒットチャートを聴かなくなって久しいので最近の曲がだいたいそうだったらごめんだし例外だった場合もごめん。
聴いたきっかけ：
「だから僕は音楽を辞めた」で真面目に感動できるくらい真面目に音楽をやっていたかった
— ふりふりモノトーン (@furifuri_mono) May 11, 2020
聴いた場所：https://youtu.be/KTZ-y85Erus
タイトルから予想できるように恋愛以外について歌っている歌だったはず。アニソンにもよくそういう良さがあって好きだがいつもそうではない。J-POPには少ないのではという印象があって，ポケモンマスターに絶対なってやるというような強い気持ちを歌ってほしい，とは普段から思う。
歌詞の内容は，「世の中で信じられている価値観（例えば「愛」とか）が分からないし，自分にはそれと違って伝えたい価値観があったはずなのだが，何らかの理由により音楽をやめた」みたいな感じだった。適当に聴いていたからなのか「何らか」が何かが分かっていないが，前提と結果が重要でそこは重要ではないか一言では表せないかみたいな気がする。
当然の反論として「愛が分からないは失恋や悲恋みたいなものではないか」があり得るが，世の中の普通の失恋ソングがそんなに共感できない人は一定数いて，愛が「失われた」については想像しかできず「そもそも無かった」ならよく分かる，みたいになりがち。両親から愛されて育っていても他人からの愛はよく分からなかったので，世の中のせいなんだと思う。そういう社会になってしまった。足切りされてしまう人にとっては恋愛は深く考える余地のないものだ。
おそらくいつの時代もだが，上の世代の価値観の拒否がここで共感を呼んでいるテーマで，自分のほしい幸せがすでにある言葉で表現できていなかったり言葉の定義が嫌いだったり，より屈折した感覚としてはかつてあった幸せの形が自分の周囲にはなかったりそれでもそれを目指せと上の世代に言われたり，みたいなところを分かっている気がする。まあこの世代について言えば，適当な単語を言っていれば団結できる時代は終わっている。最近の「敬意・感謝・絆」もよく分からなかったし。この歌がウケている世代が同世代ではないかもしれないし，作者が本当に音楽をやめたのかがどうでも良いのと同じくらいには作者の世代はどうでも良いんだけど。（実際知らない。）
歌の歌詞が聞こえない派から歌詞で大体の評価を決めてしまう派までいるのは知っているが，私はどちらかといえば聞こえない派。楽器先行の育ち方をすると認識がそうなりがち。この歌でも歌詞はどうでも良いよみたいに言っていたし，ピアノは技術があるような雰囲気を出している。
一方で，繰り返しの多さは技術はあるのにやる気がないという表現になっていたような。クラブミュージックで繰り返しは当然なので聴き慣れてはいるが，ピアノ・ギター・ベースといったバンドサウンドで前小節完全コピー（単にリズムが同じという以上に音程も同じ）を多用されると「もっとやる気を出せ」って感じる。もっとも本当にやる気ないわけではなくて，即興曲が本当に即興で作られているわけではないのと同様に意図的に情報量を落としていると思われる。間奏にアドリブあるし。
サビが5音階だった。あからさまにそうなのは1周回ってきているのかもしれない。とはいえ，歌番組でこの曲のサビだけ流されたとしたらどうでも良いよってなっていたと思うので，サビは（J-POPの）マナーとしてあるんだなあって持論が強化されてしまう。歌詞としては「結論」がサビにあったりするけど結論が一番大事かっていうとそうじゃないよねみたいな。
人との距離感，言葉の内外の区別
人との距離に応じたコミュニケーションが分かっていない。否定しているのではなく，能力が身についていないという意味で。
具体的には，そんなに親しくない相手に「誠実」な謝罪をしてしまった。
何かを発信することが目的なら，自分の主張が先にあって，どこで誰に伝えるかは後で考えても良い。インターネットではとくにそうで，文章を書いてから適切なアカウントや公開範囲を選んで投稿するという手順はブログやTwitterでは普通だと思う。
一方，相手ありきの会話では，伝えたい内容と相手は不可分だ。ゆえに難しい。伝えたい内容を言語化した時点ではまだ半分で，相手に言ったり書いたりする言葉はまた別であるべきだ。相手との関係性によっては伝えるべきでないこともあることと同様に，適切な伝え方も相手によって変わってくる。
