競プロを楽しむためのNim言語

この記事は KMC Advent Calendar 2017 - Adventar 16日目の記事です。 ついでに、 Nim Advent Calendar 2017 - Qiita の 16日目の記事でもあります。 前日のKMCアドベントカレンダーの記事は asRagi さんの 【KMCAdventCalendar2017】カンタン味玉のススメ - らぎメモ でした。

asRagiさんお誕生日おめでとうございます! 最近のasRagiさんは料理している人みたいなイメージが出来つつあります。 僕も自炊で冬を乗り切りたいです。

以下は関連記事です。

興味を持った方はこちらも御覧ください。

はじめに

競プロをやっているみなさん、C++書いていますか? ところでC++辛くないですか? 速さのために色々と犠牲にしていませんか? Nimっていう最高の言語があるんですけどお話だけでも聞いていってもらえませんか?

はい。

というわけでこの記事では競プロのような問題に Nim 最高と永遠に褒めていきます。 Nim 自体はまだver1.0にも満たない開発途中なマイナーな言語ですので、知らない方も多いと思います。 そうですね…Nimは雑にまとめると 爆速静的型付けGCありお手軽言語 とでも言えましょうか。 以降では主に似た方向の静的型付け手続き型言語との比較をしながらNimのよさを語っていきます。 Nimを知らなくても雰囲気だけ伝われば、この記事を読み終わる頃にはあなたもNimを讃える一人となっているでしょう…。

目次

  1. お手軽 マイナスインデックス配列
  2. お手軽 定数分割代入
  3. お手軽 C++連携
  4. お手軽コンパイル時計算
  5. お手軽 for文
  6. お手軽 range-based for 文
  7. DよりきれいなUFCS
  8. 楽しいオレオレ構文

お手軽 マイナスインデックス配列

問題によっては負のインデックスを使えると効率的ないしは理解しやすいことがあります。 与えられた x の範囲が -50 から 50 など負を含み、その x をインデックスとする配列が作れると楽な場合とか。 C++であれば

int data_raw[100] ; 
int *data = &(data_raw[50]) ; 
data[-10] = 72 ; 

みたいなテクでしたっけ。 さすがにポインタを使わない他の言語ではこういうことは出来ないですよね。

Nim は変態なのでできます。

var A : array[-50..50,int]
A[-10] = 72

ワーオ、変態! ちなみに、RubyPythonでは負のインデックスは配列の後ろからの番号を指しますので、 なんだか変な感じもします。

お手軽 定数分割代入

C++で入力の数値を const な状態で取得するにはどうしていますか ? 多分こうしますよね。

const int n = [](){
  int tmp = 0;
  std::cin >> tmp;
  return tmp;
}();

いいですね。安心です。 では、よくある競プロ入力な 1 2 33 444 5\n2 2 23 244 5\n3 2 33 344 5 のように 列の数が固定で決まっている場合は各行をどのように取りますか ? 上の関数を5回仮にget_int_from_stdinと名付け、こう書きますか ?

const int n = get_int_from_stdin();
const int m = get_int_from_stdin();
const int x = get_int_from_stdin();
const int y = get_int_from_stdin();
const int z = get_int_from_stdin();

にゃーん。 テンプレートを駆使すればもうちょっと行けるかもしれません。 まあでもC++テンプレートはちょっと闇なので触りたくないですね。

Nim ならこう書けます。 まずは一つ

let n = stdin.readline().parseInt()

続いて複数。

macro toTuple*(rhs: seq,cnt: static[int]): auto =
  let t = genSym(); result = quote do:(let `t` = `rhs`;())
  for i in 0..<cnt: result[0][1].add(quote do:`t`[`i`])

let (n,m,x,y,z) = stdin.readline().split().map(parseInt).toTuple(5)

ワーオ、複数分割代入最高! toTupleマクロをちょっと書く必要がありますが、これが大変便利です。 なんせ、問題に従って変数名を直感的にそのまま書くことが出来ますし、なんと全て定数です! このtoTupleマクロは、

let (n,m,x,y,z) = (let t = stdin.readline().split().map(parseInt);(t[0],t[1],t[2],t[3],t[4]))

toTuple(5) で済ましています。 (;;...;;)と複数繋げて最後が返値となるのですね. 僕が競プロでNimを使いたい理由の一つがこれです。最高です。

(注) Nim 0.18 からは構文木の構造が変わり,上記 toTupleコンパイルできなくなります. 代わりに下記をお使いください

macro toTuple*(arr: auto,cnt: static[int]): auto =
  let t = genSym(); result = quote do:(let `t` = `arr`;())
  for i in 0..<cnt: result[1].add(quote do:`t`[`i`])

お手軽 C++連携

こういう言語では C++ と連携したいことが時々あります。 例えば、ちょっと前までの Nim には PriorityQueueがありませんでした。 そんな時、C++のPriorityQueueを使えれば楽ですよね。

type
  CPriorityQueue {.importcpp: "std::priority_queue", header: "<queue>".} [T] = object
proc cNewPriorityQueue(T: typedesc): CPriorityQueue[T]
  {.importcpp: "std::priority_queue<'*1>()", nodecl.}
proc newPriorityQueue*[T](): CPriorityQueue[T] = cNewPriorityQueue(T)
proc size*[T](this: CPriorityQueue[T]):int {.importcpp: "#.size(@)", nodecl.}
proc push*[T](this: CPriorityQueue[T],x:T) {.importcpp: "#.push(@)", nodecl.}

だいたいこんな感じに書くだけで使えます。便利。 使うときも、

var pque = newPriorityQueue[int]()

のように何の問題もなく使えます。最高。 応用はこちら https://qiita.com/sessions/items/96c57a4dad9246d2cd59

お手軽コンパイル時計算

例えば素数テーブルを生成する関数を以下のように定義出来ます。

proc getIsPrimes(n:int) :seq[bool] = 
  result = newSeqWith(n+1,true)
  result[0] = false
  result[1] = false
  for i in 2..n.float.sqrt.int :
    if not result[i]: continue
    for j in countup(i*2,n,i):
      result[j] = false

はい。 これを使う時は、普通は

let isprimes = getIsPrimes(100)
echo isprimes[17]

のように使います。キーワード let で宣言しているので、 この関数の計算は実行時に行われます。 コンパイル時に計算したければ

const isprimes = getIsPrimes(100)

と、 letconst に変えるだけ!超便利! C++ だと constexpr の制約があったり、そもそも関数をconstexpr にしないと いけなかったり、色々めんどくさいですよね!Nim最高!

お手軽 for文

この節では 0 から n まで昇順列挙するfor文について述べます。

個人的に競プロのfor文のREPの文化が好きです。 REP は大抵以下のようなマクロです。

#define REP(i,n) for(int i = 0 ; i < (int)(n) ; ++i)

このマクロは以下のように使用できます。

REP(i,20) std::cout << i << std::endl; 

もちろん、#define によるマクロが悪であることなどは言うまでもありませんが、 競プロに類する問題ではこれは効率的な記法として一定の支持を集めていることは 否定出来ないと思います。 range-based-forと違ってインデックスがとれれば配列の中身を変更できるし インデックスを元にして別の変数と連携して計算できる基本的で最も使用される文なので、 そこが最適化されてしまえばこうなるのでしょう。

はい。

ところで kotlinだと

for (i in 0..20) print(i)

と書けますが、i の範囲は [0,20] であり、

for (i in 0 until 20) print(i)

と書かないと i の範囲を [0,20) に出来ません。 一貫性がなくてめんどい。 D言語だと iota を作ったりします。

さて、Nim はこんな感じで書けます。

for i in 0..<20: echo i

ここの < に注目です。これがあるとiの範囲は[0,20)になり、 これがなければ、iの範囲は[0,20] になります。 わかりやすいですね。これはswiftでも同じです。 最高ですね。

お手軽 range-based for 文

C++ には range-based for文があります。

for(auto d: data) std::cout << d << std::endl;

便利ですね。 しかしながら、そのインデックスを取得するのはちょっとめんどいです。

for(const auto& d:data) auto index = &d - &data[0];

にゃーん。

D言語のrange-based for文は

foreach(d;data) writeln(d);

のように書け、インデックス付きは

foreach(i,d;data) writeln(i," ",d);

のように書けます。かなりいいですね。 ただ、何重にもなると foreachと書くのもちょっと長いような気もします。

ところで Nim は簡潔に書けます。

for d in data: echo d

d の型は勝手に推論してくれるので C++のように auto とか書かなくてもよくて便利です。 index が欲しければ

for i,d in data: echo i," ",d

と書けて便利です。

DよりきれいなUFCS

D言語のUFCS、実はちょっと癖があって使いにくいです。 クラス内で宣言するメンバ関数とUFCSで擬似的にそう見える関数と二重に 定義出来てしまうせいで、ごちゃごちゃしてしまうことがあります。 Nim はメンバ関数とかはなく全て普通の関数記法で書き、モジュール内でエクスポートするものとしないもので分ける設計なのでそのような心配はありません。 Nim 最高!

楽しいオレオレ構文

template times*(n:int,body:untyped): untyped = (for _ in 0..<n: body)
template `max=`*(x,y:typed):void = x = max(x,y)
template `min=`*(x,y:typed):void = x = min(x,y)

の3つを主にオレオレ構文として定義しています。

# n回 hoge と出力
n.times: 
  echo "hoge"

とか、

# data[i][j] = max(data[i][j],data[j][k]) と同義
data[i][j] .max= data[j][k]

とか。 times は ただのforと比べて変数が増えないし便利ですね。 C++の雑魚マクロと違って本当に変数が増えないんですよ? マクロ定義に使用した変数 _ は使う側では見えないんですよ? 最高じゃないですか? C++のマクロって本当にクソですよね?

max=+= のノリで max を適用した感じのオレオレ構文です。 お行儀悪いですが地味に便利なので使ってしまいます。

最後に

以上、Nimの便利だと思う機能をつらつらと書かさせていただきました。 ここまで読んでくださり、ありがとうございました。

Nimに興味を持たれたら、 Nim Advent Calendar 2017 - Qiita を読んだり、 Nim Programming Language を読んだりしてください。

明日のKMC AdventCalendar は id:kazakami さんによる MinecraftでFPGA - kazakami_9’s diary です! マイクラFPGAいいですね、いいです、すごくいいです。