[Derivation] Gray Code

這學期的 Computational Intelligence 的第二個作業提到了要用Gray Code來做encoding。雖說我還在考慮整個作業是不是要用Haskell來寫，不過gray code的generator應該蠻好寫的。比起imperative language應該會有個比較乾淨的寫法。

首先，為了先來個直覺的pointwise版。來看一下兩個很簡單的情況：

length = 1 => [[0],[1]]
length = 2 => [[0,0],[0,1],[1,1],[1,0]]

我們可以考慮第二個case是由兩個部份構成[0,0],[0,1] 和 [1,1],[1,0]。很明顯, 前段是把 0 接上 [0],[1]，而後段是把 1 接上 [1],[0]。而"[1],[0]"是"[0],[1]"的inverse！

根據上面的觀察結果
我們可以定義出第一版的gray-pw為

gray-pw 0 = [[]]
gray-pw (n+1) = let hypo = gray-pw n in
    (map (0:) hypo) ++ (map (1:) (reverse hypo))

--
待續 :
1) point-free版本
2) deriving for faster