CODEWITHSUNDEEP
haskell
dinsim
dinsim

Reputation: 2465

Reversing binary numbers in Haskell

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 ?

Upvotes: 2

Views: 1891

Answers (6)

primodemus
primodemus

Reputation: 516

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)

Upvotes: 0

sth
sth

Reputation: 229563

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.

Upvotes: 2

ephemient
ephemient

Reputation: 204668

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

Upvotes: 4

poke
poke

Reputation: 387507

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

Upvotes: 6

Aidan Cully
Aidan Cully

Reputation: 5507

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.

Upvotes: 8

Don Stewart
Don Stewart

Reputation: 137937

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.

Upvotes: 1

Related Questions