Haskell／Clojureで数値をN進数表記に変換

去年からHacker Rankが面白くてハマっている。 今年に入ってからHaskellを始めたので、ますます関数型プログラミングでアルゴリズムをやりたい気分が上がっている。

アルゴリズム勉強したいなと思い、 有名なKnuth先生の「The Art of Computer Programming」を買って、 ちょっと読んでみたら、これアセンブラなんですね。興味を削がれたのでそっと積んで置く・・・。

一方、Hacker Rankに飽き足らず、コードパズル系の本も気になっていて、 「プログラマ脳を鍛える数学パズル」も買ってみた。書籍だと解説もあるので楽しみである。

早速、しょっぱなの２問をやってみた。問題自体はいいのだが、 回答がプログラミング言語の機能をばんばん使う前提にしているんだな。 (rubyのevalレベルまで使っていいとは）

制限時間が設定されていて、とにかく速く問題を解くことに目が置かれているので、 そうしているんだな。

別にいいんだけど、 しかしまあ、美味しい部分は、その端折ったところにあったりする。

1問目は、同じ整数を表す10進・8進・2進表記が回文になっている数を求める問題なのだが、 N進数に変換する部分はプログラミング言語のライブラリを使っていい前提だ。

・・・このN進数表記に変換する部分が美味しい部分ですやん。

実際、Clojure, Haskellで書いてて面白く楽しかった部分だ。 やっていること自体は難しくないが、最大公約数を求めるユークリッドの相除法みたく、 数学に近い部分の本質的な面白さがある。

これは、関数型言語で書くと短くて鑑賞のしがいのあるコードが書ける。 （最近はコードを書いて悦悦と眺めるのが目的みたいな感じになっている。 そのために良問を探している感がある。）

さて、ある数をN進表記に変換する関数を、まずはHaskellで書いてみる。

どんな関数かというと、整数10を2進表記に変換する場合に、

Prelude > n_ary_str 10 2
"1010"

という風に使う関数だ。

import Data.Char

n_ary :: Int -> Int -> [Int]
n_ary 0 _ = []
n_ary num base = n_ary quotient base ++ [remainder]
                 where
                    quotient = num `quot` base
                    remainder = num `mod` base

n_ary_str :: Int -> Int -> String
n_ary_str num base = map intToDigit (n_ary num base)

やっていることは、 まずN進の数字のリストを求めて、それを文字列にしている。

n_ary 10 2 は [1, 0, 1, 0] というリストが返る。 これを使ってn_ary_str関数で、順に文字に置換しているだけだ。 Haskellの文字列は文字の配列なので、置換したら終わり。

10進以上は対応していないが、対応するのは簡単だ。

たとえばn_ary 199 16は[12, 7]になるが、これを['C', '7']に変換するだけだ。 つまり、10以上の数字を'A'からのアルファベットに置き換えるだけ。

Haskellは習い始めだが、whereというシンタックスはえらく感動する。 これを使うとコードの本質的な部分を先に書けて意図を強調できる。

上記コードは、別に使わなくてもいいのに、わざわざwhereを使っているが、 結局N進数って何？という問いに対して、ソースコードで、 「Nで割った余りを求める。自分の上の桁に対して商を与えそれを繰り返す」です、と表現できる。 （Nに相当する部分がソースではbase）

Haskellは本当にそのまま定義を書ける感じだ。大学の授業とかで使って欲しい言語No.1だな。

Clojureも同じように書ける。（n_ary関数だけ）

(defn n_ary [number base]
  (if (zero? number)
    []
    (let [quotient (quot number base)
          remainder (mod number base)]
    (conj (n_ary quotient base) remainder))))

たぶんLISPerはこんな冗長なコードは書かない(笑。

自分のいつものClojureのコードだと下記のようになる。（文字列変換も込みで）

(defn n_ary [number base] 
  (loop [n number,
         res []]
    (if (zero? n)
      res
      (recur (quot n base)
             (cons (mod n base) res)))))

(defn n_ary_str [number base]
  (apply str (n_ary number base)))

Clojureのloopマクロは本当に便利で多用している。 すごく便利なのだが、実は初見だとコードがわかりづらいかもしれないね。