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 ?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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)