初めに
drken さんの記事の10問をF#で解いてみました.
元記事はこちらです. https://qiita.com/drken/items/fd4e5e3630d0f5859067
目的
F#はいわゆる関数型言語ですが,mutable変数や.Netの恩恵が受けられるという事があって個人的に面白くかけるなぁという印象のある言語です.イチ押しはパイプライン演算子というやつで,この記事では主にその魅力をアピールしたいと思います.
(堪能というわけではないのと,僕自身は普段の競技プログラミングにはC#で参加しているので,多少の訛りや不格好な点は大目に見ていただければ..)
パイプライン演算子
F#におけるパイプライン演算子|>
は,いわゆるUNIX/LINUX系のシェルでサポートされているパイプ|
のような動作をする演算子です.
ある型a
の値 x
を受け取って違う型b
の値を返す関数をf
とするとき,F#の記法では
// f : x :a -> b a型の値xを受け取ってb型の値を返す関数
let y = f x
と書くことでx
に f
を作用させた値を y
で受け取る(束縛)事が出来ます.数学で出てきたようなy = f(x)
という書き方に似ています.パイプライン演算子はこれを単純に書き順をひっくり返すものになります.
// f : x :a -> b a型の値xを受け取ってb型の値を返す関数
let y = x |> f
これで何が嬉しいかというと,f
を作用させた結果にさらにg
を作用させた結果を得たいような局面で,次のように
// f : x :a -> b a型の値xを受け取ってb型の値を返す関数
// g : y :b -> c b型の値yを受け取ってc型の値を返す関数
let z = g (f x)
と書かないといけないところが,パイプライン演算子を使うことで
// f : x :a -> b a型の値xを受け取ってb型の値を返す関数
// g : y :b -> c b型の値yを受け取ってc型の値を返す関数
let z = x |> f |> g
という風にどんどん右側につないでいくことでができるようになります.C#のLINQやjQueryのメソッドチェーンと同じような印象ですが,つなぎ目で型がつながっていればどんどんつないでいける点で,こちらの方がかなり自由度が高い記述が可能です.
(例えばLINQだとIEnumerableが途切れてしまうようなメソッド(例えば.Sum()
)の後につなげられるメソッドはないですが,パイプライン演算子ならその結果にさらにほかの関数を作用させたりできます)
さらに頼もしいのが,F#は関数の部分適用をサポートしているので,1つの引数に作用させて違う結果を得るような関数を手軽に作ることができるという点です.
月並みな例だと,例えば次の足し算add
は引数を2つとる関数ですが,「1つだけ与えておいてスタンバっている関数」を作ることができれば,(少し語弊はありますが)それは1つの引数を受け取って値を返す関数とみなすことができます.これを部分適用と呼んでいます.
// add0 : (x,y) : (int * int) -> int
// int型の値の組(x, y)を受け取ってint型の値 (x + y)を返す関数 (x と yの両方がそろわないと動かない)
let add0 (x, y) = x + y
// add : x: int -> y:int -> int
// int型のxを受け取って,(int型のyを受け取って intの値 x + y を返す関数)を返す関数
let add x y = x + y
// add には x を適用させただけの状態で意味がある(部分適用)
let f = add x // こう書くことで f : int -> int が得られる
// fに束縛しなくてもそのまま使うこともできる
let z = 12 |> (add 9) // z = 21
// 演算子の優先順位と型推論により括弧も省略できる
let w = 32 |> add 16 // w = 48
前置きが長くなりましたが,実例を見ていきましょう.
回答
第1問: ABC086 A - Product
open System
let inputArray = stdin.ReadLine().Split(' ') |> Array.map int
let a = inputArray.[0]
let b = inputArray.[1]
let f x y = if (x % 2) = 0 || (y % 2) = 0 then "Even" else "Odd"
f a b |> printfn "%s"
標準入力をうけとっているのはstdin.ReadLine().Split(' ')
で,これはいかにもC#っぽい書き方ですが,これは1行読んだ文字列を' '
区切りにしてstring
の配列(Array
)に変換したものを返します.
その後ろにパイプライン演算子|>
が早速登場しています.
Array.map f ar
は後ろに2つ引数をとります.1つ目の引数f
がmapの内容,2つ目の引数ar
が作用させるArrayになり,ar
の各要素にf
を作用させた結果を要素に持つArray
を返します.ここではf
にあたるint
はint型へのparseであり,ar
にあたる部分にstdin.ReadLine().Split(' ')
がパイプライン演算子で持ってこられているという感じです.
最終行も同様で,f a b
の結果にprintfn "%s"
を作用させていて,意味としてはprintfn "%s" (f a b)
と同じになるわけです.(printfn
はprintf
プラス改行(n)らしいです)
第 2 問: ABC 081 A - Placing Marbles
open System
stdin.ReadLine()
|> Seq.sumBy (fun c -> if c = '1' then 1 else 0)
|> printfn "%d"
文字列中にある'1'
の数を数える問題です.
fun
はいわゆるラムダ式をつくる構文で,(fun c -> if c = '1' then 1 else 0)
はc:char型が'1'なら1
,それ以外は0
を返す関数を作っています.Seq.sumByは第1引数の関数を用いて各要素を計算した値を合計する関数です.文字列はF#ではchar型のシーケンス(Sequence)として扱うことが可能です.
第 3 問: ABC 081 B - Shift Only
open System
let N = stdin.ReadLine() |> int
let A = stdin.ReadLine().Split(' ') |> Array.map int
// 180504 加筆:canDiv2は 0入力で無限ループするので注意
//(今回は問題の制約で0が入力されない事が保証されている)
let rec canDiv2 = fun v -> if v % 2 = 1 then 0 else (1 + canDiv2(v / 2))
A
|> Array.map canDiv2
|> Array.min
|> printfn "%d"
与えられた配列Aの各要素に対して,2で何回割ることができるかを計算して,その最小値を求める問題です.
ここではcanDiv2
という関数を定義していますが,キーワードrec
を付けることで再帰定義が可能になります.また,F#のif
は文ではなく式であるため,必ず値を持ちます.canDiv2
では奇数なら1
,偶数なら2で割った結果をcanDiv2
で計算した結果に1を足す,という再帰で関数の値が決まっています.
パイプライン演算子は改行でどんどんつないでいくのが,F#の慣例的なコーディングスタイルのようです.
第 4 問: ABC 087 B - Coins
open System
let readInt () = stdin.ReadLine() |> int
let A = readInt ();
let B = readInt ();
let C = readInt ();
let X = readInt ();
[ for i in [0..A] do
for j in [0..B] do
for k in [0..C] do
yield i * 500 + j * 100 + k * 50]
|> List.sumBy (fun v -> if v = X then 1 else 0)
|> printfn "%d"
A
枚以下の500円とB
枚以下の100円とC
枚以下の50円でX
円を作る方法がいくつあるかという問題です.
ここではリストの内包表記というものを使って(コード中の[]
で囲まれた部分),実際にi * 500 + j * 100 + k * 50
の取りうる値が全て入ったリストを作成しています.F#のリストはいわゆる線型リストで実装されているようで,実際に領域を確保して生成されます.
リストを遅延評価で生成する方法もあります.シーケンスというものを使います.
open System
let readInt () = stdin.ReadLine() |> int
let A = readInt ();
let B = readInt ();
let C = readInt ();
let X = readInt ();
seq {for i in 0..A do
for j in 0..B do
for k in 0..C do
yield i * 500 + j * 100 + 50 * k}
|> Seq.sumBy (fun v -> if v = X then 1 else 0)
|> printfn "%d"
第 5 問: ABC 083 B - Some Sums
open System
let readIntArray () = stdin.ReadLine().Split(' ') |> Array.map int
let [| N; A; B |] = readIntArray ()
let digSum n =
n
|> string
|> Seq.sumBy (fun c -> int c - int '0')
[1..N]
|> Seq.sumBy (fun v -> if (digSum v >= A) && (digSum v <= B) then v else 0)
|> printfn "%d"
1
からN
までの間に桁和がA
以上B
以下になるものがいくつあるかという問題です.
コード中のlet [| N; A; B |] = readIntArray ()
の部分は,F#の型推論・パターンマッチの出番ですが,3
要素の配列の0
番目1
番目2
番目の要素をそれぞれN
A
B
に束縛するという指定で書くことができます.N
A
B
の方はreadIntArray
から推論されます.
(一般にはreadIntArray
が3
要素とは限らないのでコンパイル時にはその意のwarningがでます)
第 6 問: ABC 088 B - Card Game for Two
open System
let readInt () = stdin.ReadLine() |> int
let readIntArray () = stdin.ReadLine().Split(' ') |> Array.map int
let N = readInt ()
let A = readIntArray () |> Array.sortWith (fun a b -> a.CompareTo b |> (*) -1);
let rec takeFirst xs =
match xs with
| [] -> 0
| x :: [] -> x
| _ -> xs.[0] + takeFirst (List.skip 2 xs)
let total = A |> Array.sum
let alice = Array.toList A |> takeFirst
let bob = total - alice
printfn "%d" (alice - bob)
N
枚のカードの山から互いにカードを取っていくというのを,それぞれが最大化した際に合計にどれだけの差が最終的につくかという問題です.降順にソートして交互に取っていくイメージです.
パターンマッチということで,takeFirst
という関数を考えて,Aliceの手番に取るスコアの計算しています.
降順にソートされたA
に対して
・要素数0
なら何も取れない(= 0
)
・要素数1
ならそれをとる (= x
,リストが[x]
という形)
・それ以外なら,1つ目をとって(2つ目はBobがとるので)スキップ
という風にして,0,2,4,..
番目の値を足し合わせた値を返す関数がtakeFirst
です.
第 7 問: ABC 085 B - Kagami Mochi
open System
let readInt () = stdin.ReadLine() |> int
let N = readInt ()
let A : int [] = Array.zeroCreate N
for i in [0..N-1] do A.[i] <- readInt ()
A
|> Array.distinct
|> Array.length
|> printfn "%d"
真に昇順となる列の最長の長さを求める問題です.異なる数字がいくつあるかをかぞえるので,それ自体はArray.distinct
という関数があります.
ここで初めてでてきたのは,Array.zeroCreate
という関数で,これは第一引数の数だけのデフォルト要素をもつ配列を生成します.Array.zeroCreate
はジェネリックな関数であるため,返り値を受ける変数に型情報を与えてやることで,所望の型の配列を作ります(let A : int []
の部分で int []
だと教えている)
もう一つ配列の重要な特徴に,各要素がmutable(可変)であるということがあります.この例ではA
のi
番目の要素A.[i]
にreadInt ()
の値を代入しています.代入は<-
を使います.
第 8 問: ABC 085 C - Otoshidama
open System
let readInt () = stdin.ReadLine() |> int
let readIntArray () = stdin.ReadLine().Split(' ') |> Array.map int
let [| N; Y |] = readIntArray ()
let showResult (a, b, c) = printfn "%d %d %d" a b c
seq { for i in [0..N] do
for j in [0..(N - i)] do
yield (i , j, N - i - j)}
|> Seq.tryFind (fun (a, b, c) -> a * 10000 + b * 5000 + c * 1000 = Y)
|> (fun opt -> if Option.isSome opt then Option.get opt else (-1, -1, -1))
|> showResult
合計N
枚の10000円札,5000円札,1000円札でY
円が作れるか,作れるなら一つ作り方を答えろという問題です.
10000円札の枚数と5000円札の枚数から1000円札の枚数が決まるという事から,10000円札の枚数と5000円札の枚数を総当たりして探すという解法です.ここでも作りえる組み合わせのシーケンスを作って,そこから探す(tryFind
)という方針をとります.
tryFind
はOption型という値を返します.これはNone
(失敗)であるか,Some
(成功)であって値があるという成功失敗に関する戻り値を付随させるような型です.成功したなら値をもってきているのでその値を採用し,なければ(-1, -1, -1)
にするという感じですね.
第 9 問: ABC 049 C - Daydream
open System
let S = stdin.ReadLine()
let N = S.Length
let dp : bool [] = Array.zeroCreate (N + 1)
let candi = [ "dream"; "dreamer"; "erase"; "eraser" ]
dp.[0] <- true
for i in [0..N-1] do
if dp.[i] then
candi |> List.iter (fun str -> if (i + str.Length <= N && S.Substring(i, str.Length) = str ) then (dp.[i + str. Length] <- true))
if dp.[N] then "YES" else "NO"
|> printfn "%s"
"dream", "dreamer", "erase", "eraser" の4つをうまく結合させて文字列S
を作ることができるかという問題です.この問題は300点にしては難しいと思ったら,後ろから見れば一意にとって行けるという性質があったようですが,思いつかずにdpをしてしまいました.
配列はmutableという性質があるので,時には思い切って書けるというのも,ゆるふわでいいものだと思います.
第 10 問: ABC 086 C - Traveling
open System
let readInt () = stdin.ReadLine() |> int
let readIntArray () = stdin.ReadLine().Split(' ') |> Array.map int
let N = readInt ()
let TXY : (int * int * int) [] = Array.zeroCreate (N + 1)
TXY.[0] <- (0, 0, 0)
for i in [1..N] do
let [| x; y; z |] = readIntArray ()
TXY.[i] <- (x , y , z)
let check (((t0, x0, y0) , (t1, x1, y1)) : (int * int * int) * (int * int * int)) =
((x0 + y0) % 2 = t0 % 2) && ((x1 + y1) % 2 = t1 % 2) && (Math.Abs(x0 - x1) + Math.Abs(y0 - y1) <= t1 - t0)
TXY
|> Array.pairwise
|> Array.map check
|> Array.reduce (&&)
|> (fun b -> if b then "Yes" else "No")
|> printfn "%s"
時刻と座標が時系列に沿って与えられるので,その通りに移動できるかという問題です.
問題の本質は,時刻の偶奇とX + Y
の偶奇が一致しているかということとマンハッタン距離が時間以下に収まるかということで判定できるという部分で,ここはコーディングよりも考察ウェイトが大きいです.
このコードでは check
という関数でそれをチェックしています.型推論の手掛かりがないため,引数に型注釈(:
で型を明示できる)をつけています.型推論できない記述があるときはコンパイルが通りません.
ちょっと物珍しい関数としては,Array.pairwise
という関数があって,これは配列内の隣接要素をタプルにした配列を作るという関数です.つまり
[| 1; 4; 6; 8; 9 |] |> Array.pairwise
は
[| (1, 4) ; (4, 6); (6, 8); (8, 9) |]
になります.上の回答コードでは (T, X, Y)
のタプルの配列を作って,今と1手先とのペアの配列を作って,それぞれチェックするという感じになっています.Array.reduce
は全要素を第1引数の関数で演算してつないだ結果を返す関数です.
おわりに
パイプライン演算子の魅力がどれくらい伝わったかは疑問があるような記事になってしまったかもですが,Haskellに挫折した人でも.Netに抵抗がなければゆるふわ関数型への導入としてF#は楽しいと思うので,興味がわいた方はぜひやってみてください.
F#が使える競技プログラミングサイトは意外と少ないので,atcoderで使えるというのは練習にいいですね.yukicoderでも使えます.
いつかC#にパイプラインと部分適用が導入される日を夢見てます.