Gibt es eine effiziente Möglichkeit, eine unäre Zahl in eine binäre Zahl umzuwandeln?
Stellen diese Datentypen unäre bzw. binäre natürliche Zahlen dar:
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...)
Meine Frage ist: Gibt es eine Möglichkeit, die Funktion zu implementieren:
toBNat :: UNat -> BNat
Das funktioniert inO(N), nur ein Durchgang durch UNat?