algorithm - 有什么有效的方法可以将一元数转换为二进制数？

Question

让这些数据类型分别表示一元和二进制自然数:

data UNat = Succ UNat | Zero
data BNat = One BNat | Zero BNat | End

u0 = Zero
u1 = Succ Zero
u2 = Succ (Succ Zero)
u3 = Succ (Succ (Succ Zero))
u4 = Succ (Succ (Succ (Succ Zero)))

b0 = End                   //   0
b1 = One End               //   1
b2 = One (Zero End)        //  10
b3 = One (One End)         //  11
b4 = One (Zero (Zero End)) // 100

(Alternatively, one could use `Zero End` as b1, `One End` as b2, `Zero (Zero End)` as b3...)

我的问题是:有没有办法实现这个功能:

toBNat :: UNat -> BNat

这在 O(N) 中有效，只通过 UNat 一次？

Answer 1

我喜欢其他答案，但我发现他们的渐近分析很复杂。因此，我提出了另一个具有非常简单的渐近分析的答案。基本思想是为一元数实现 divMod 2。因此:

data UNat = Succ UNat | Zero
data Bit = I | O

divMod2 :: UNat -> (UNat, Bit)
divMod2 Zero = (Zero, O)
divMod2 (Succ Zero) = (Zero, I)
divMod2 (Succ (Succ n)) = case divMod2 n of
    ~(div, mod) -> (Succ div, mod)

现在我们可以通过迭代divMod转换为二进制。

toBinary :: UNat -> [Bit]
toBinary Zero = []
toBinary n = case divMod2 n of
    ~(div, mod) -> mod : toBinary div

渐近分析现在非常简单。给定一元表示法中的数字 n，divMod2 需要 O(n) 时间来生成一半大的数字——也就是说，它最多需要 c*n 足够大的 n 时间。因此，迭代此过程会花费很多时间:

c*(n + n/2 + n/4 + n/8 + ...)

众所周知，这个级数收敛于c*(2*n)，所以toBinary也是O(n)，witness constant 2 *c.