CoffeeScriptで配列のシャッフル

日本語では２冊めになるCoffee本（たぶん）を見てたら、
（Windowsユーザを対象にした敷居の低い本で、それはそれで価値があると思うのですが）
配列をシャッフルしてるコードがあって、それがいかにも昭和レトロなコードだと感じたので、
自分ならこう書くだろうというのを試しに書いてみました。

配列のシャッフル(ワンライナーで)

arrayShuffle.coffee

Array::shuffle=->(->(p=(Math.random()*(i+1))|0;[@[p],@[i]]=[@[i],@[p]])for i in [@length-1..0]by -1;@).call([@...])

ちなみに、rubyならこんな感じなのでしょう
（そもそもrubyにはArray#shuffleがあるから書く必要はないけど）。

arrayShuffle.rb

class Array
  def shuffle
    while x=a.delete_at(rand a.size) do r.push x end 
    r
  end
end

こうして書いてみると、CoffeeScript の入門用の題材として
要点を概ね盛り込んだコンパクトなものになっていて、
学習用にも使えそうなのでここに解説つきで残しておきます。

手順の概要

1. 配列を a としたとき、a[0..i] の区間から要素をランダムに１つ選び、a[i] と入れ替える
2. i を 配列の最後の添字（a.length-1）から0まで変化させながら上記を行う
3. それが終了した時点で aはシャッフルされている

注

• 上記手順で書いた通りに配列を変数aで受けても勿論OKだけど、
  　 Coffeeらしい字面に慣れるためプログラムでは@を使うようにしました。
• i を変化させる範囲は、１までで十分ですが、0まで行っても大丈夫なプログラムにしました。

交換

分割代入が使えるので、乱数で選んだ添字をpとしたとき、[@[i],@[p]] = [@[p],@[i]] で交換できます。

• 右辺も左辺も、分割代入の際は配列リテラルのようにブラケット［］で囲むのですね。
• ちなみにRubyでは a,b=1,2 のように右辺左辺ともに 囲まずにカンマ区切りで並べていいし
  a,b=[1,2] のように左辺だけ囲んでもいいようです。

ランダムによる選択

Rubyだとrand()に整数を渡すと整数の乱数を生成してくれるけど、
JS/CSにはありません。なので、Math.random() で生成した[0,1) の範囲の実数を、
i+1 倍してから小数点以下を切り捨てて整数化、という手順になります
（i は対象範囲の要素数ではなく範囲の末端の添字としてある）。
実数 r を整数化する真当な方法は Math.floor(r) ですが、
短く書ける裏ワザとしては parseInt(r) (文字列経由で変換)や、
ｒ | 0 （ビット演算の前に整数化するらしい）が知られています。
ただし、可読性はだいぶ犠牲になりますね。

繰り返し

sz=a.length （ちなみに .size というメソッドはないようですね）とすると、
for i in [sz-1 .. 0 ] で、前述の手順に沿った降順のループが作れます。
ちなみに Rubyの 3..1 や Scalaの 3 to 1 は 降順にならず空の範囲（あくまで昇順）を作ります。
Coffeeだと、上限..下限 で指定すると降順の数字の並びを作ってくれて楽ですね。
と思ったら、実はここに落とし穴が一つ。油断は禁物。便利な機能が悪さをするというケースです。
配列 a が空配列のとき、[sz-1..0] は [-1,0] という 昇順の範囲を生成してしまい、
プログラムは正常に動作しなくなります。空配列までを考慮した場合、

1. [0...sz].reverse() を使う（ここではピリオド３つで上限値の１つ手前までの範囲を指示できる）
2. for i in [sz-1..0] by -1 と、マイナスの増分値を指定する

のいずれかで回避しましょう。
もしくは、配列そのものを使ってインデックス付きのループ sz-i-1 for _,i in a にするという方法もあります。
ここでは for の後ろに配列要素と添字を受ける変数名を並べますが、
前者は使わないので無名のプレースホルダー _ を置いてます。
このプレースホルダー '_' は、RubyでもScalaでも同じ文字ですね。

配列のコピー

JS/CS のArrayには、非破壊のメソッドは少ないようです。
これまでに見てきた手順にしても、もとの配列を破壊（並び替え）しながら進行していきます。
破壊的メソッド群を活用して行く上でも、必要に応じてもとのオブジェクトのコピーをとっておけるよう
習慣付け若しくは心の準備が必要ですね。
本稿では非破壊的メソッドを作ることにします。
そのために、予め配列のコピーを作っておきましょう。
ruby の a.dup 、Scalaの a.clone のようなメソッドは見当たらなかったので、
代わりの方法を考えましょう。
ここでは深いコピーである必要はないので、
オリジナルと同じサイズの新たな配列を作って、そこのオリジナルの各要素を詰め込めればいい訳です。
for構文の練習を目論んでるかのような実例をよく見かけますが、
以下のようにすればもう少し簡便に複製が作れるようですね。

1. [].concat a 空配列の後ろに連結
2. new Array(a...) splatで展開して流し込めるのがCoffeeのメリット
3. [a...] これもイディオムとして定着すれば可読性の心配はしなくていいだろう

メソッドにする

CoffeeScriptは オープンクラス（Rubyコミュニティ的な言い方かなこれ）が実現されています。
CSの既存クラスにメソッドを追加するには、Array.prototype.shuffle=-> ..... という形で、
オブジェクトの prototype属性に関数を代入すればいいのですが、これはJS的書き方で、
CSの場合、Array::shuffle= ..... という記法が用意されているようです。

まとめる（関数で包む + スコープへの配慮）

これまでのコードをとりまとめて、バージョン１として以下のようなコードを書きました。

version1.coffee

Array::shuffle=->
	a=[@...]
	for i in [(a.length-1)..0] by -1
		p=(Math.random()*(i+1))|0
		[a[p],a[i]]=[a[i],a[p]]
	a

ところが、以下のようなケースで、a と b について違う結果が得られます。
関数を作る場面でCSは変数のスコープを作らないから、ということだと思われます。
関数の中で一時変数のつもりでａという名前を使いましたが、
ここで作った関数でのスコープは外側に開かれたスコープなので、
外側に変数 ａ　があれば内部で新たにｖａｒ宣言をせずに
中と外で共用にしてしまうのでしょう。

test1.coffee

a=[] ; b=[]		# JS的にはここでvar宣言される
Array::shuffle=->
	a=[@...]
	for i in [(a.length-1)..0] by -1
		p=(Math.random()*(i+1))|0
		[a[p],a[i]]=[a[i],a[p]]
	a
a=[1..10] ; a.shuffle()
b=[1..10] ; b.shuffle()
console.log(a)		# => シャッフルされた結果
console.log(b)		# => もとの配列

ｒｕｂｙやCSのように変数宣言しないでいい言語は、楽な点も多々あるけど、
こういう落とし穴もあることを知っておかないと困るということですね。
対策としては２つが考えられます。

1 局所（のつもりの）変数名として他と重ならない余程奇妙な名前を使う
2 関数で閉じ込める

せっかく矢印１つで関数が作れる言語に踏み込んだんだからここでは2で行きましょう。

version2.coffee

Array::shuffle=->(->
	for i in [(@length-1)..0] by -1
		p=(Math.random()*(i+1))|0
		[@[p],@[i]]=[@[i],@[p]]
	@
	).call([@...])

@が目立つコードになりました。慣れないと読みづらいコードですね。
ちなみに、＠は、JSのthisに変換されるもので、
メソッド呼び出しではレシーバに相当するオブジェクトを指します。
関数オブジェクトに対して.call や .apply メソッドを呼んだ時は、
その呼出の第一引数で渡したものが＠に束縛されることになってます。
version2.coffee では .call（）のカッコ内の＠ が 元の配列で、
その他の（局所関数の中で使われている）＠は、
コピーされた配列（が.call()を通してメソッド呼び出しの主体ヅラをしているところ）を表しています。
this.length が @.length とも@lengthとも書けることもチェックしておきましょう。

ワンライナーにする

と、見出しを振ってみましたが、無理にワンライナーにする必要はありません（見にくいだけだし）。
CS布教のためにワンライナーを誇示したいときだけ使えばいいのかも知れません
（ちなみに私がワンライナーを作ったのは後述の事情によるものでした）。
一行にしたければ基本的には改行を取り去ってつなげていけばOKだと思います。
ただ、for文（と呼ぶのが適切かどうかも自信ないのですが、つまり前置のforですね）については、
改行して字下げしてfor 配下の行がどこまでの範囲かを示す、という方法以外に、
範囲を示す方法が（未だに）わかっていません。（）でも｛｝でも囲めないようでした。
なので後置のforに置き換えました。
後置のforは (式1 ； 式2 ...) for 変数 in 範囲 という書き方ができます。
その結果が、冒頭に示した一行のコードです。

公式リファレンスに書かれていないこと

ついでに書いておきますと、前置のforは、公式リファレンスには書かれてませんでした
（皆さんどうやってこれが使えることを知ったんだろう）。
もう１つ、REPLについても、リファレンスはさらっとしか書いていませんね。
私はREPLで複数行の入力が可能であることを昨日まで知りませんでした
（もっとクールにプログラミングというページで教わりましたが、
そういえば前述のCoffee本にも書かれてなかったなあ）。
Ctrl-V を叩けばよかったのですね。
他にも、.help などの ピリオドで始まるREPLコマンドがいくつかあります（これは自力で発見した）。
こうした基本的な情報不足が、せっかくの面白い言語の敷居を上げてしまってるようにも思いました。