Reversing binary numbers in Haskell

Question

I have defined data type for Binary numbers as follows

data Bin = Nil | O Bin | I Bin 
           deriving (Show, Eq)

i want to define a function reverse :: Bin -> Bin so that when i give input like

reverse (I (O (I (I Nil)))) i should get the outut I (I (O (I Nil))) that means reversed as input, any body please give me hint how i can do this ?

Just for inside information, even though this is someone else's definition, they're combining the ideas of a list and a binary number when it is much easier to keep them separate and then merge them together. This is essentially the point of haskell: composition of pieces. Just realize if you had to type the definition that there is better (Aidan Cully's Solution). — codebliss
– codebliss, Commented Dec 14, 2009 at 15:31
I probably wouldn't create any new types at all: Bool is already a suitable bit type, and [] is already a suitable list type. Making the type Bin = [Bool] alias, maybe. — ephemient
– ephemient, Commented Dec 16, 2009 at 21:03

Aidan Cully · Accepted Answer · 2009-12-13 22:09:05Z

8

Why are you doing this this way? Why not something like this:

data Bit = I | O
newtype Bin = List Bit

Then you could just use the Prelude's reverse operation directly...

Edit A simple substitution from the Prelude's function:

reverse x = rev x []
  where
    rev [] a = a
    rev (x:xs) a = rev xs (x:a)

yields:

reverse x = rev x Nil
  where
    rev Nil a = a
    rev (I xs) a = rev xs (I a)
    rev (O xs) a = rev xs (O a)

The thing is, your type is very similar to the list type:

data List a = a : (List a) | []

so the logic for the List routines applies directly to your type.

edited Dec 13, 2009 at 22:09

answered Dec 13, 2009 at 21:55

Aidan Cully

5,52726 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

dinsim Over a year ago

no, the thing is i am not allowed to change the data type, i have to do it in the given data type

Rotsor Over a year ago

newtype Bin = List Bit does not make sense. You may have meant type Bin = List Bit or newtype Bin = List [Bit] or newtype Bin = Bin (List Bit) or something similar.

poke · Accepted Answer · 2009-12-13 22:22:51Z

6

data Bin = Nil | O Bin | I Bin deriving (Show, Eq)
reverse :: Bin -> Bin
reverse x = rev Nil x
    where
        rev a Nil = a
        rev a ( O b ) = rev ( O a ) b
        rev a ( I b ) = rev ( I a ) b

answered Dec 13, 2009 at 22:22

poke

392k80 gold badges595 silver badges631 bronze badges

Comments

ephemient · Accepted Answer · 2009-12-13 23:20:18Z

4

binToList Nil = []
binToList (O a) = False : binToList a
binToList (I a) = True : binToList a

listToBin [] = Nil
listToBin (False : xs) = O (listToBin xs)
listToBin (True : xs) = I (listToBin xs)

reverseBin = listToBin . reverse . binToList

answered Dec 13, 2009 at 23:20

ephemient

206k39 gold badges292 silver badges402 bronze badges

3 Comments

Charles Stewart Over a year ago

listToBin can be made into a fold: listToBin = foldr (\ b d -> if b then (I d) else (O d)) []

ephemient Over a year ago

Or even foldr (\b -> if b then I else O) [].

ephemient Over a year ago

Or even foldr ((!!) [O, I] . fromEnum) [], if you were feeling particularly point-free today.

sth · Accepted Answer · 2009-12-14 01:43:02Z

2

GHC's List module defines the reverse function on lists like this:

reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

The helper function rev uses its second element as an accumulator that stores the reversed part up to the current position. In each step the first element of the remaining input list is added to head of the accumulator that is passed to the recursive function call.

The same principle can be applied to your binary number type to reverse the order of the digits.

edited Dec 14, 2009 at 1:43

answered Dec 13, 2009 at 21:50

sth

231k56 gold badges288 silver badges370 bronze badges

2 Comments

dinsim Over a year ago

I am not sure i can apply list comprehension here because i have input like (I (O (I (I Nil))))

sth Over a year ago

Yes, you probably cannot use a list comprehension.

Don Stewart · Accepted Answer · 2009-12-13 21:58:26Z

1

Seems odd that you're defining both a list type, and a type for bits. I think I'd reuse the base libraries list type [] and just set the elements to be your bit type, as Aidan shows above.

answered Dec 13, 2009 at 21:58

Don Stewart

138k36 gold badges372 silver badges472 bronze badges

Comments

primodemus · Accepted Answer · 2009-12-26 04:53:54Z

0

this is a possible solution:

reverseBin :: Bin -> Bin 
reverseBin b = revBin b Nil
            where revBin Nil acc   = acc
                  revBin (I b) acc = revBin b (I acc)
                  revBin (O b) acc = revBin b (O acc)

answered Dec 26, 2009 at 4:53

primodemus

5162 silver badges8 bronze badges

Collectives™ on Stack Overflow

Reversing binary numbers in Haskell

6 Answers 6

2 Comments

Comments

3 Comments

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

2 Comments

Comments

3 Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related