Reversing binary numbers in Haskell

Tag: haskell Author: ptyy1314 Date: 2009-11-27

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).
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.

Best Answer

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.

comments:

no, the thing is i am not allowed to change the data type, i have to do it in the given data type
Thanks a lot Aidan,
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.

Other Answer1

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

Other Answer2

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

comments:

listToBin can be made into a fold: listToBin = foldr (\ b d -> if b then (I d) else (O d)) []
Or even foldr (\b -> if b then I else O) [].
Or even foldr ((!!) [O, I] . fromEnum) [], if you were feeling particularly point-free today.

Other Answer3

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.

comments:

I am not sure i can apply list comprehension here because i have input like (I (O (I (I Nil))))
Yes, you probably cannot use a list comprehension.

Other Answer4

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.

Other Answer5

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)

Relate

© Copyright ask.programmershare.com.

Design by ask.programmershare.com