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

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

如果我们有一个递增 BNat 的函数，我们可以通过运行沿着 UNat 很容易地做到这一点，在每一步递增 BNat ：

toBNat :: UNat -> BNat
toBNat = toBNat' End
    where
    toBNat' :: BNat -> UNat -> BNat
    toBNat' c Zero     = c
    toBNat' c (Succ n) = toBNat' (increment c) n

现在，这是 O(NM)，其中 M 是 increment 的最坏情况。所以如果我们可以在 O(1) 中做到 increment，那么答案是肯定的。

这是我尝试实现 increment:

increment :: BNat -> BNat
increment = (reverse End) . inc' . (reverse End)
    where
    inc' :: BNat -> BNat
    inc' End      = One End
    inc' (Zero n) = One n
    inc' (One n)  = Zero (inc' n)

    reverse :: BNat -> BNat -> BNat
    reverse c End = c
    reverse c (One n) = reverse (One c) n

此实现是 O(N)，因为您必须 reverse BNat 才能查看最低有效位，因此总体上 O(N)。如果我们考虑 BNat 类型来表示反转的二进制数，我们不需要反转 BNat，并且正如@augustss 所说，我们有 O(1)，它给你 O(N ) 总体。

Answer 2

要递增二进制数字，您必须翻转数字末尾的第一个零及其前面的所有零。此操作的成本与输入末尾 1 的数量成正比（为此，您应该将数字表示为从右到左的列表，例如列表 [1;0;1;1] 代码为 13） .

设a(n)为n末尾1的个数：

a(n) = 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...

让

s(k) = a(2^k) + a(2^k+1) + ... + a(2^(k+1)-1)

是 2 的两次幂之间的元素之和。您应该能够说服自己 s(k+1)=2*s(k) + 1（其中 s(0) = 1），注意

    a(2^(k+1)) ..., a(2^(k+2) - 1)

是由

拼接得到的

    a(2^k) + 1, ..., a(2^(k+1) - 1) and   a(2^k), ..., a(2^(k+1) - 1)

因此，作为几何级数，s(k) = 2^k - 1。

现在增加 N 次数字的成本应该与

成正比

    a(0) + a(1) + ... + a(N)
  = s(0) + s(1) + s(2)  + ... + s(log(N)) 
  = 2^0 - 1 + 2^1 -1 + 2^2-1 + ... + 2^log(N) - 1
  = 2^0 + 2^1 + 2^2 + ... + 2^log(N) - log(N) - 1
  = 2^(log(N) + 1) - 1 - log(N) - 1 = 2N - log(N) - 2

因此，如果您注意从右到左表示您的数字，那么朴素算法是线性的（请注意，如果您确实需要相反的方式，您可以执行列表反转并保持线性).

Answer 3

我喜欢其他答案，但我发现他们的渐近分析很复杂。因此，我提出了另一个具有非常简单的渐近分析的答案。基本思想是为一元数实现 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)中，见证常数2*c。

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

Is there any efficient way to convert an unary number to a binary number?

algorithm

haskell

functional-programming

lambda-calculus