Addition of Binary Numbers in Haskell

Question

I need to create a function to add a binary number to another one. It's a task for my study and I'm not that much into Haskell and could use some help.

I already made the datatype which I have to use.

data B = Zero
    | Even B
    | Odd B
    deriving (Show, Generic)
instance Listable B where tiers = genericTiers

Even means 0, Odd means 1 and Zero is the end.

..so for example Odd(Even(Odd Zero))) is equal to 101 ... and that is my function so far.

plusB :: B -> B -> B
plusB (Odd a) (Odd b) = Odd (Even (plusB a b))
plusB (Even a) (Even b) =  Even (plusB a b)
plusB (Even a) (Odd b) = Odd (plusB a b)
plusB (Odd a) (Even b) = Odd (plusB a b)
plusB (Zero) (Zero) = .....

I think that I have to use recursion for it to work.

I hope that makes sense.

Well you likely should work with two parameters here, since your function adds two numbers together. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Jun 23, 2020 at 19:49
I don't understand your code at all. First, I don't understand your data type: what does Odd $ Even $ Odd $ Odd Zero represent? Second, why derive Generic? Third, you declare plusB :: B -> B -> B, but your implementations have the type B -> B instead of B -> B -> B. Finally, (plusB x) and ((plusB x)) are equivalent, which seems unlikely to be correct. — OpenAI was the last straw
– OpenAI was the last straw, Commented Jun 23, 2020 at 20:37
@AndrewRay The type is isomorphic to [Bool], and it's pretty easy to translate that to a binary number. The number you ask about is either 1011, or 1101, depending on whether the intended encoding is LSB first or last. — amalloy
– amalloy, Commented Jun 23, 2020 at 21:10
This is really more of an algorithm question, rather than a Haskell one. What you currently have is basically a half adder; read up on how to extend that to a full adder. If you have a question regarding a concrete problem in you implementation for that in Haskell, that could make for a good question here. — leftaroundabout
– leftaroundabout, Commented Jun 25, 2020 at 10:34

jpmarinier · Accepted Answer · 2020-06-25 16:22:03Z

If you assume that the Even constructor returns the image of an even number, and that the Odd constructor returns the image of an odd number, this implies that the outermost constructor maps to the rightmost (least significant) bit.

In that case, more descriptive names for Odd and Even could be Twice and TwicePlus1.

Mapping B objects to Integers:

toIntegerFromB :: B -> Integer
toIntegerFromB  Zero    =  0
toIntegerFromB (Even x) =  2*(toIntegerFromB x)
toIntegerFromB (Odd x)  =  1 + 2*(toIntegerFromB x)

As for the addition of two B objects:

plusB :: B -> B -> B

we have 3*3 = 9 equations to write. But 5 of them involves Zero which is the neutral element, and so are quite easy to write:

plusB  (Zero)    (Zero)     =  Zero
plusB  (Zero)    (Even a)   =  Even a
plusB  (Even a)  (Zero)     =  Even a
plusB  (Zero)    (Odd a)    =  Odd a
plusB  (Odd a)   (Zero)     =  Odd a

Regarding the 4 remaining equations, we note that number 1 maps to Odd Zero and that number 2 maps to Even (Odd Zero).

Thinking of Odd and Even as TwicePlus1 and Twice respectively:

(Odd a) + (Odd b) ≃ (2a+1)+(2b+1) = 2 + 2*(a+b) ≃ Even (Odd Zero) + Even (a+b)

Hence the equation:

plusB  (Odd a)   (Odd b)    =  plusB  (Even (Odd Zero))  (Even (plusB a b))

Next, we have:

(Odd a) + (Even b) ≃ (2a + 1) + (2b) = 1 + 2*(a+b) ≃ Odd (a+b)

Hence, using symmetry, the 2 equations:

plusB  (Even a)  (Odd b)    =  Odd  (plusB a b)
plusB  (Odd a)   (Even b)   =  Odd  (plusB a b)

The last remaining equation is easier:

(Even a) + (Even b) ≃ (2a)+(2b) = 2*(a+b) ≃ Even (a+b)

plusB  (Even a)  (Even b)   =  Even (plusB a b)

Putting it all together:

plusB :: B -> B -> B
plusB  (Zero)    (Zero)     =  Zero
plusB  (Zero)    (Even a)   =  Even a
plusB  (Even a)  (Zero)     =  Even a
plusB  (Zero)    (Odd a)    =  Odd a
plusB  (Odd a)   (Zero)     =  Odd a
plusB  (Odd a)   (Odd b)    =  plusB  (Even (Odd Zero))  (Even (plusB a b))
plusB  (Even a)  (Even b)   =  Even (plusB a b)
plusB  (Even a)  (Odd b)    =  Odd  (plusB a b)
plusB  (Odd a)   (Even b)   =  Odd  (plusB a b)

Compared to the more common data Nat = Zero | Succ Nat, this representation has the nice advantage of requiring only O(log(n)) nested constructors, instead of O(n).

Collectives™ on Stack Overflow

Addition of Binary Numbers in Haskell

1 Answer 1

Putting it all together:

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Putting it all together:

Comments

Your Answer

Sign up or log in

Post as a guest

Related