競技プログラミングのためのF#入門¶

• created: 2022/11/28

サンプルコード¶

ごちゃごちゃと説明を読むよりもコードをさっと見たい人も多いでしょう. データ構造とアルゴリズム, さらには私の競プロのコードを集めたAlgorithmsAndDataStructureByFSharpを参考にしてください. 特に次の2ファイルが役に立つでしょう.

• Arithmetics.fsx
  • 競プロ用のmodつき階乗・順列・組み合わせの例を収録している.
  • その他n進展開とその復元などお役立ち関数も収録.
• Reference.fsx
  • 基本は公式リファレンスの参照用まとめ.
  • サンプルが即実行できるように一緒に載せている.
  • 処理したい内容から日本語で検索しやすいように日本語も添えている.
  • Haskellとは関数名が違う場合にその情報を添えている.
  • Haskellにある便利関数がない場合はその実装を載せている.

基本的に収録しているF#コードのインデントは標準の4ではなく2です.

C#との相互運用¶

.NETの資産が使えます. F#との相性は必ずしもよくないものの, 入門レベルでも.NETの破壊的なQueueはよく使います. F#標準の非破壊的なQueueはないようです.

F#開発環境構築¶

• インストール関連はメンテナンスが大変なため省略します. 公式情報を参照してください.
• インストールが面倒ならTry F#があります.
• Microsoft製なのもありVSCode+ionideがお勧めです.
  • 私はお気に入りエディタがEmacsだからEmacsで書いています. 特に勧めません.
• 拡張子fsxでF#をスクリプト言語のように書いて使えます.
  • 参考: 私のGitHub中のコード
  • 例えば具体的にはABC042/B_fs_01.fsx
  • 2022/11時点で私はfsxでしかF#のプログラムを書いた経験がありません.
• fsx+REPLを使うと気持ちよく書けます.

F#入門¶

まずは命令型的なコードの直移植に役立つ要素から解説し, 関数プログラミング的な最小限の解説をします. 競技プログラミングの実コードが大量にあるため例はほぼ割愛します.

一般的な特徴¶

• cannorinさんのF#を知ってほしいを読んでください.

(可変な)変数定義¶

• (不変な)変数はlet a = 1のようにletで定義します.
• 可変な変数はlet mutable a = 1とmutableをつけて宣言します.
• 可変な変数<-を使ってa <- 2で書き換えられます.

for文¶

• ScalaやKotlinと違い, F#でforは式でなく文です.
• 0から10までカウントアップのループを作るには次のように書きます.

1
2

for i in 0..10 do
  pritfn "%A" i

• 逆にカウントダウンは次のように書きます.

1
2

for i in 10..(-1)..0 do
  printfn "%A" i

データ構造は配列を例にする¶

• F#にも配列・リスト・辞書・集合・キューなどのデータ構造があります.
• .NET標準・共用の場合もあればF#独自の場合もあります.
• いちいち全て挙げていては煩雑なため以下の説明では配列で通します.

配列リテラル¶

• [|1;2;3|]のように書きます.
  • ちなみにリストは[1;2;3]です.
• 配列の区切り文字はOCamlと同じくセミコロン;です.
• [|1..10|]と書くと連番で生成します.
• [|1..2..9|]と書くと2刻みの配列を生成します.

配列の参照¶

• 配列の各要素はa.[i]で取れます.
• Pythonでのa[i]などと違ってドット(.)が必要です.
• OCamlの丸括弧流a.(i)とも違います.
• ちなみにHaskellではデータ型に応じてa !! iやa ! iと!演算子を使います.

forの二つの役割: 新たな配列作成・結果の積み上げ¶

• 競技プログラミングでは配列の処理が重要です.
• 配列処理用の代表的な関数はmapとfoldです.
• これらの違いを考えるにはforの使い方を考え直す必要があります.
• forの典型的な使い方は次の二つです.
  • ある配列から新たな配列を作る: map系の処理.
    • 例: 配列の各要素を二倍にする.
  • ある配列から新たな値を作る: fold系の処理.
    • 例: intの配列の和を取る.
    • イメージとしてはたたみ込むループ.
• 既に説明を書いて添えたように, 上記の二通りの意図・目的でmapとfoldを使い分けます.
• 以下mapとfoldを便利に使うためにいくつか準備します.

関数の定義¶

• 変数と同じく, 次のようにletで定義します.

1
2
3
4
5

#r "nuget: FsUnit"
open FsUnit

let f x y = x + y
f 2 3 |> should equal 5

• 引数が複数ある場合, CやPythonなどと違ってカンマ区切りではなくスペース区切りで書きます.
• 無名関数はfun x y -> x + yのように定義できます.
• 無名関数も変数に束縛できます.

1
2
3
4
5

#r "nuget: FsUnit"
open FsUnit

let f = fun x y -> x + y
f 2 3 |> should equal 5

• 再帰関数を定義するときはlet rec f xのようにrecキーワードが必要です.

関数の部分適用¶

• F#やHaskellをはじめとしたいわゆる関数型言語では関数の部分適用があります.
• 有名な例は次の例です.

1
2
3
4
5
6

#r "nuget: FsUnit"
open FsUnit

let plus x y = x + y
let plus2 x = plus 2 x
plus2 3 |> should equal 5

• 例えばPythonでは関数が第一級のオブジェクトであるため, 返り値として関数を返せます.
• F#も同じで関数の返り値として関数が返せます.

パイプライン演算子|>¶

• F#の特徴的な要素です.
• 例えばHaskellでも同じ役割のData.Functor.&があるものの, ほとんど見かけません.
• これを多用するのがF# wayです.
• Unixコマンドに慣れているならまさにUnixのパイプラインのように扱えます.
• オブジェクト指向系の言語に慣れているなら, とりあえずはメソッドチェーンのように思えばいいでしょう.
• 例はこれからmapとfoldの中で取り上げます.
• 実際のコードも参照してください.
• 次のように考えるとF#のプログラムを書きやすいはずです.
  • 基礎のデータを用意する.
  • 自作コマンドのように書き捨ての関数(無名関数)を作る.
  • Array.mapやArray.foldに自作コマンドを部分適用させて処理をつなげる.

map¶

• まずはmapを取り上げます.
• 配列の全ての要素を二倍にする簡単な例は次のように書けます.

1
2
3
4
5

#r "nuget: FsUnit"
open FsUnit

[|1..5|] |> Array.map (fun i -> i*2)
|> should equal [|2;4;6;8;10|]

• もっとシンプルに次のようにも書けます.

1
2
3
4
5

#r "nuget: FsUnit"
open FsUnit

[|1..5|] |> Array.map ((*) 2)
|> should equal [|2;4;6;8;10|]

• 一般に演算子を括弧でくくると関数化できるため, それを使って表記を簡潔にしています.
• ここでまさにパイプライン・部分適用が出てきます.
  • 元データが配列[|1..5|]
  • 各要素を二倍する関数としてfun x -> x*2
  • 全体に適用するのがArray.map
• これがF#スタイル, ひいては関数プログラミングの基本的な構造です.
• 部分適用は次の通りです.
  • Array.map: ('T -> 'U) -> 'T array -> 'U array
  • Array.map ((*) 2): 'T array -> 'U array
• まさに配列を新たな配列に変換する関数ができています.
• これでmapと自作コマンドとしての無名関数の組み合わせ(部分適用)でデータを処理するフローができました.

fold¶

• foldの典型例は配列の総和です.

1
2

[|1..3|] |> Array.fold (fun acc i -> acc + i) 0
|> should equal 6

• Array.foldは次の構造を持ちます.
  • 型: ('State -> 'T -> 'State ) -> 'State -> 'T array -> 'State
  • 第一引数: 個々の要素を処理する関数
  • 第二引数: 初期値
  • 第三引数: 元データの配列
• つまり先のコードは元データの[|1..3|]に対して, 型'T array -> 'Stateを持つ関数Array.fold (fun acc i -> acc + i) 0を作用させています.
• 初期値の'Stateが遠くに0と書かれているとわかりにくいため, F#では次のようにも書けます.

1
2

(0,[|1..3|]) ||> Array.fold (fun acc i -> acc + i)
|> should equal 6

• Array.foldの前の演算子が||>でパイプライン|が二本になっています.
• これも慣れると便利です.
• ちなみにF#には配列の和を取る関数としてArray.sumがあるため, 上の処理は素直にArray.sum [|1..3|]で十分です.
• もう一つ, 初期値として配列の先頭の値を取りたい場合にはArray.reduceがあります.

1
2
3
4

#r "nuget: FsUnit"
open FsUnit

[|1..3|] |> Array.reduce (+) |> should equal 6

配列処理関数の最後の引数は配列¶

• 部分適用で関数をつなげて処理を書きやすくするための大事な特徴です.
• これに気をつければ部分適用でパイプライン処理がつなげられます.
• ただしArray.foldBackのような重要な例外があります.
  • OCamlのfold_rightと同じ引数の順番です.
  • Haskellのfoldrとは違います.
  • Haskellコードを読むとき・参考にするときには注意してください.

再帰関数¶

• いわゆる関数型言語で真っ先に取り上げられるテーマです.
• その一方で実際のプログラムでそこまで使われないとも言われる要素です.
• 実際のプログラムで直接的に再帰がそこまで使われない理由は簡単で, mapやfoldを使うからです.
• そしてmapやfoldで書ける処理は再帰でも書けます.
• むしろmapやfoldはパイプライン演算子・部分適用とセットにして処理全体を書きやすくするための再帰の構文糖衣と思うといいでしょう.
• もちろん再帰でないと書けない・再帰の方が書きやすい処理もあります.
  • 例えばSeqで無限リストを作って処理を回しでもしない限り, 無限ループは再帰でないと書けません.
• 逆に言えばmapやfoldには再帰の強さを制限して無限ループのような嫌な振る舞いをおさえる役割もあります.
• 再帰関数自体は他の言語にもある概念で, 競技プログラミングでも良く使われる要素でもあるため, これ以上は詳しくは説明しません.

return¶

• RubyやScalaと同じくF#は最後に評価した式を返すためreturnは必要ありません.
• F#のreturnはコンピュテーション式の中で独自の意味を持つため, 下手にreturnを使うとエラーが出ます.

その他の配列処理¶

• 個別のコードで確認する方が理解もしやすいため, ここでは最小限の要素だけ説明します.
• 公式のリファレンスや, それを実行・参照しやすくまとめたReference.fsxも参考にしてください.
• 配列中の不要な要素を削りたい: filter関数.
• ある基準をもとにグループ化したい: groupBy関数
• 和を取りたい: sumまたはsumBy関数
• ある要素を含むか知りたい: contains関数
• i番目の要素を取得したい: get関数またはa.[i]

注意¶

剰余の処理¶

他の言語のコードを参考にする場合は気をつけるべき要素です.

F#は負の数の剰余を考えると負の数が出てきます. 特にF#では(-1) % 1000 = -1です. 一方例えばPythonでは(-1) % 1000 = 999です. この挙動が問題になる場合は剰余を取りたい数を足してから剰余を取りましょう. 特にF#では((-1) + 1000) % 1000 = 999が得られます.

入出力の基礎¶

注意¶

私は以下のテンプレートを使っています. 注意を箇条書きにします.

• テンプレートそのままではエディタのエラーが出ます. 使うたびに必要なところだけ見繕って削ってください.
• 競技プログラミングではintの範囲でおさまらない処理が多いため, int64を基本にするのが無難です.
• コードの確認用に簡単なテストを実行できるようにしていて, 最初の#r "nuget: FsUnit"と最後のshould equalはテストライブラリの読み込みと実行です. 提出用コードには含めません.

入門レベルの入出力なら下記コードの多少のバリエーションでまかなえます. 私の勉強が進んでもっと凝った入出力テンプレートが必要になってきたら追記・修正します.

記号選択¶

• AtCoderの問題文でよく大文字が出てくるため, F#の流儀よりもAtCoderの文章との対応を重視してNやMを使っています.
• リストはXs, 配列はarrayからXa, シーケンスはXqのように書きます. リストにxsをあてるのは少なくともHaskellでは標準的な記法で, それを採用しています. そしてF#はasが予約語で自由に使えないため, 変数名の先頭を大文字にしているのは変数名Asを使いやすくするための処置でもあります.

テンプレート¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#r "nuget: FsUnit"
open FsUnit

System.IO.Directory.SetCurrentDirectory __SOURCE_DIRECTORY__

let solve Xa =
  let MOD = 1_000_000_007L
  System.Int32.MaxValue
  System.Int64.MaxValue
  1

let N = stdin.ReadLine() |> int64
let M = stdin.ReadLine() |> bigint.Parse
let D,X = stdin.ReadLine().Split() |> Array.map int64 |> (fun x -> x.[0],x.[1])
let Xa = stdin.ReadLine().Split() |> Array.map int64
let Aa = Array.init N (stdin.ReadLine() |> int64)
let Aa = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int64 |> fun x -> x.[0],x.[1])
let Alls = Console.ReadLine() |> Seq.initInfinite |> Seq.takeWhile ((<>) null)
let S = stdin.ReadLine()
solve Xa |> Array.map string |> String.concat " " |> stdout.WriteLine
solve Xa |> Array.iter stdout.WriteLine
solve Xa |> stdout.WriteLine

solve Aa |> should equal 1