S-99: Ninety-Nine Scala ProblemsのP07を末尾再帰にするだけの正月だった

昨年大晦日から、少しずつS-99: Ninety-Nine Scala Problemsに取り組んでいる。 取り組み方は色々あると思うが、個人的に設定したルールは以下の二つ。

• Listのコンストラクタ(Nil or ::)以外は自作する
• なるべく末尾再帰にこだわる(なぜ末尾再帰にこだわるか)

これで現時点(2018/01/08)ではP26まで解いていたのだが、P07・P26においては技量が足らず末尾再帰化を諦めていた。 しかし私の中のリトル佐藤が、年始休暇も終わるというのにこの体たらくでは悔いが残るといっているので、せめてP07だけでも末尾再帰化することにした。

まず、問題はこいつ。

P07 (**) Flatten a nested list structure.
Example:
scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8)

注意したいのはflattenのシグニチャが def flatten(list: List[Any]): List[Any] となるところだろうか。 例えばこいつが def flatten[A](list: List[List[A]]): List[A] であれば問題は簡単で、以下のように書けば良いはずだ。

def flatten[A](list: List[List[A]]): List[A] = {
  @annotation.tailrec
  def go(acc: List[A], list: List[List[A]]): List[A] = list match {
    case Nil       => acc
    case e :: rest => go(addAll(acc, e), rest)
  }

  go(Nil, list)
}

しかし、実際のシグニチャが def flatten(list: List[Any]): List[Any] であることにより、末尾再帰を諦め、以下のコードとなってしまっていた。 このコードでは、縦(Listのネスト)方向にも横(Listの要素)方向にも再帰をしなければならないため、再帰(goの部分)が二回出現している。

def flatten(list: List[Any]): List[Any] = {
  // TODO 末尾再帰にできぬ...できぬのだ!!
  def go(acc: List[Any], maybeList: Any): List[Any] = maybeList match {
    // Listの場合
    case e :: rest => go(go(acc, e), rest)
    case Nil       => acc
    // それ以外
    case e         => e :: acc
  }

  P05.reverse(go(Nil, list)) // P05では末尾再帰のreverseを定義している
}

しばし、こういう場合は末尾再帰にできないものと考えていた。 しかし、正月休みで休養・アルコール・気合が充分な状態で再度検討してみると、goが縦・横方向への再帰のため二回出現しているから末尾再帰ができないのだから縦横で別々の関数を使うようにすれば末尾再帰化できるのではないか、と考えた。

このアイデアを用いて書いたコードがこれ。

@annotation.tailrec
def flatten(list: List[Any]): List[Any] = {
  // もちろん、addとかaddAllは自前で末尾再帰化したコードを用意している
  @annotation.tailrec
  def go(acc: List[Any], list: List[Any]): List[Any] = list match {
    case (l: List[Any]) :: rest => go(addAll(acc, l), rest)
    case e :: rest              => go(add(acc, e), rest)
    case Nil                    => acc
  }

  // 型注釈を付けないとコンパイル通らない理由はいずれ調査されるだろう...
  if (forall(list, (e => !e.isInstanceOf[List[Any]]): Any => Boolean)) {
    list
  } else {
    flatten(go(Nil, list))
  }
}

予想通り、再帰の方向で別々の関数に分ければ末尾再帰化できた。

この解法が汎用的に使えるかどうかを考えるにはちょっと酔っ払いすぎていてよくわからないけども、とにもかくにも前に進むことができた。

AutoHotKey事始

勤務先の個人用PCがシンクライアント＋仮想デスクトップに移行するため、このままでは英字配列のHHKBが使えなくなってしまう。
対応策として、以下の二点を考え付いた。

1. HHKBとシンクラの間で物理的にJP配列を英字配列に変換する
2. 仮想デスクトップ上のアプリケーションの前で英字配列に変換する

前者は手軽に行うのは難しそうなので断念し、後者をAutoHotKeyで実現することにした。

パクった参考にしたサイトは以下の通り。
http://ahk.xrea.jp/index.html
http://qiita.com/844196/items/9fc1cd8470a9ad9c3a69

とりあえず、今の設定はこんな感じ。
一番右上のチルダのキーが効かないのが悩み。

*"::send, @
*&::send, {^}
*'::send, &
*(::send, *
*)::send, (
*+0::send, )
*=::send, _
*^::send, =
*~::send, {+}
*@::send, [
*`::send, {{}
[::send, ]
*+{::send, {}}
*]::send, \
*}::send, |
*+::send, :
+*::send, "
LWin::LAlt
LAlt::LWin
RWin::Send, {vkF3sc029}
*vkBA::send, '

JavaScriptで文字コード値⇔文字列変換

作成中のアプリにてエラーメッセージが文字コードで出力されたので、文字列に変換する処理を書いてみた。

/**
 * 文字コード値→文字列
 */
function (cd) {
    var cdArr = cd.replace(/\\u([0-9a-fA-F]{1,4})/g, function () {
        return parseInt(arguments[1], 16) + ',';
    }).split(',');
    return String.fromCharCode.apply(String, cdArr);
}

ついでに逆の処理も書いた。

/**
 * 文字列→文字コード値
 */
function (str) {
    var i = str.length, temp = new Array(i);
    if (str === '') return '\\u0000';
    while (i--) {
        temp[i] = '\\u' + ('000' + str.charCodeAt(i).toString(16)).slice(-4);
    }
    return temp.join('');
}