F#で競技プログラミング
書いてる人のステータス
https://gyazo.com/b137e747332711c9411ccdc506673590
うん……
MLやりたいよな〜という気持ちがあった
よいこと
Listがパターンマッチと相性がいい理由とか
x::lみたいなのが気持ちいい
再帰を通して分割統治のセンスを磨けた(気がする)
考えたものをそのままプログラミングできる
頭の中にある概念をコードに落とすときに、並べかえをしたりフラットにしたりする必要がない
例えば、累積和が欲しいと思ったときに
code:fsharp
// arrayの区間和を累積和使って求めたい！
let sum=
// arrayの累積和を出す
// |>はパイプライン演算子。後ろに置いた関数を前の値に適用する
// Array.scanはfoldの各ループごとの状態を並べるイメージ
// 演算子は()で囲めば関数になる。+は二項演算子なのでこの場合 int->int->int になる
let s=array |> Array.scan (+) 0
// [i,j)の区間和を求める。このようにインデントされた部分の最後に書かれた式の値がその部分の値になる
他の言語だとこうもいかない
累積和を出す部分を「並べかえ」てsumの定義の前に出し、「フラットにし」てsumと同じスコープで書く必要がある
他にもseqを使って手続き的に候補を列挙した後に関数的な操作を適用したり、そもそも|>が便利だったりする
どうでもいいこと
MapやSetがImmutable
想定解法がC++のstd::unordered_mapとかを想定してたりして計算量的に怖くて使えない std::unordered_mapはハッシュベースなので大体の操作が$ O(1)で完了するけど、F#のMapは平衡二分木ベースなので$ O(log N)かかる Hash-Array Mapped Trieがほしい
永続で操作が$ O(1)で完了するとかいう夢のようなデータ構造
比較も要求しないしよさそう
定数倍が重い罠、あると思います
よくないこと
標準ライブラリがあんまり(というかかなり)充実してない
Queueない
BFSどう書くねんになる
結局自分で書く羽目になった
関数型言語において(?遅延評価前提かも)QueueなしでBFSできるという話を見たことがあるが，本当？ Heapがない
割と多くの問題で困る
かった
popcntがない
これはdotnetcoreの問題らしい(?)
x86 intrinsicなやつならあるらしいが…
世にあるコードがあんまり参考にならない
(F#やOCamlなのに)dpテーブル埋めてたりする
関数型言語なんだからできる限りメモ化再帰で書いてほしいのです
配るdpは許されるよね
手続き型機能もあるにはあるけどbreakもcontinueもないんだからただの劣化C#になってしまう
使えないコンテストのほうが多い
JOIとかだとC/C++しか使えないので、競プロ極めたいと思ってるならやめたほうがいい
そもそも競プロ極めたいなら計算機の気持ちを知るべきなので末尾再帰がwhileに変換される…ということにリソースを割くよりも問題をループ使って解くことに割いたほうがいいと思う