(/^^)/⌒●~*$ a(){ a|a& };a

きょうと…のだいがく？にかよってるんですけど！

競プロに疲れた人のNim言語

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

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

はじめに

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

目次

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

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

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

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

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

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

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

お手軽 定数分割代入

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回仮にint_from_stdinと名付け、こう書きますか ?

const n = int_from_stdin();
const m = int_from_stdin();
const x = int_from_stdin();
const y = int_from_stdin();
const z = int_from_stdin();

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

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

let n = stdin.readline().parseInt

続いて複数。

macro unpack*(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).unpack(5)

ワーオ、複数分割代入最高！ unpackマクロをちょっと書く必要がありますが、これが大変便利です。 なんせ、問題に従って変数名を直感的にそのまま書くことが出来ますし、 なんと全て定数です！ このunpackマクロの詳細は長くなるので割愛します。 僕が競プロでNimを使いたい理由の一つがこれです。最高です。

お手軽 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]()

のように何の問題もなく使えます。最高。

お手軽コンパイル時計算

時間の制約がちょっと気になる時、これがすごく便利なんですよ。 例えば素数テーブルを生成する関数を以下のように定義出来ます。

proc getIsPrimes(n:int) :seq[bool] = # [0...n]
  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)

と、 let を const に変えるだけ！超便利！ C++ だと constexpr の制約があったり、そもそも関数をconstexpr にしないと 行けなかったり、結構めんどくさいですよね！最高！

お手軽 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(auto& d:data) auto index = &d - %data[0];

にゃーん。

D言語のrange-based for文は

foreach(d;data) writeln(d);

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

foreach(i,e;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 は全部UFCSとして設計されているのでそのような心配はありません。 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と比べて変数が増えないし便利ですね。 max= は += のノリで max を適用した感じのオレオレ構文です。 お行儀悪いですが地味に便利なので使ってしまいます。

最後に

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

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

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