灵感来自：用Scala解Hanoi塔

Hanoi塔

一个普通的value-level的实现，用作参考。

hanoi :: Int -> String-> String -> String -> IO ()
hanoi 1 from to tmp = putStrLn $ from ++ " -> " ++ to
hanoi n from to tmp = do
    hanoi (n - 1) from tmp to
    hanoi 1 from to tmp
    hanoi (n - 1) tmp to from

完全的type-level实现

完整代码

这是我第一个想到的实现，我觉得也是最简单、最函数方式的：

{-# LANGUAGE TypeOperators  #-}
{-# LANGUAGE TypeFamilies #-}

data Zero
data Succ a

data from :-> to
data act1 :>> act2
infixr :>>

type family Hanoi n from to tmp :: *
type instance Hanoi (Succ Zero) from to tmp = from :-> to
type instance Hanoi (Succ (Succ n)) from to tmp =
    Hanoi (Succ n) from tmp to
        :>> Hanoi (Succ Zero) from to tmp
        :>> Hanoi (Succ n) tmp to from

from :-> to表示把盘子从from移动到to，act1 :>> act2表示先执行act1再执行act2。Hanoi就是个type function，以类型作参数，返回类型，整个实现其实就是根据类型构造类型。

data Left
data Middle
data Right

type Three = Succ (Succ (Succ Zero))

x = undefined :: Hanoi Three Left Right Middle

在ghci中查看x的类型就能得到结果：

ghci> :t x
x :: ((Left :-> Right)
      :>> ((Left :-> Middle) :>> (Right :-> Middle)))
     :>> ((Left :-> Right)
          :>> ((Middle :-> Left)
               :>> ((Middle :-> Right) :>> (Left :-> Right))))

虽然不太好看，但是结果是对的（可以写个Show实例就能有好看的效果）。

原来的scala的实现是在隐式转换的时候进行IO操作，打印出结果。Haskell没隐式转换，编译和运行又明确分离，要在类型推导的过程中执行IO操作几乎是不可能的的（不知道Template Haskell能不能）。

不管是Haskell还是Scala的实现，盘子数都不能太多，否则ghc类型推导时要大量内存，而scala会生成一个太大的方法，JVM运行不了。