Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell Decimal to Binary

I am trying to build a function that converts a Decimal(Int) into a Binary number. Unfortunately other than in java it is not possible to divide an int by two in haskell. I am very new to functional programming so the problem could be something trivial. So far I could not find another solution to this problem but here is my first try :

 fromDecimal :: Int -> [Int]

fromDecimal 0 = [0]
fromDecimal n = if (mod n 2 == 0) then 
                do

                0:fromDecimal(n/2) 

                else 
                do  
                1:fromDecimal(n/2) 

I got an java implementation here which I did before :

   public void fromDecimal(int decimal){
    for (int i=0;i<values.length;i++){

        if(decimal % 2 = 0)
        values[i]=true ; 
        decimal = decimal/ 2;
        else {values[i]= false;
        }       }
}

Hopefully this is going to help to find a solution!

like image 841
disccco Avatar asked Dec 07 '22 12:12

disccco


1 Answers

There are some problems with your solution. First of all, I advise not to use do at all, until you understand what do does. Here we do not need do at all.

Unfortunately other than in java it is not possible to divide an int by two in haskell.

It actually is, but the / operator (which is in fact the (/) function), has type (/) :: Fractional a => a -> a -> a. An Int is not Fractional. You can perform integer division with div :: Integral a => a -> a -> a.

So then the code looks like:

fromDecimal :: Int -> [Int]
fromDecimal 0 = [0]
fromDecimal n = if (mod n 2 == 0) then 0:fromDecimal (div n 2) else 1:fromDecimal (div n 2)

But we can definitely make this more elegant. mod n 2 can only result in two outcomes: 0 and 1, and these are exactly the ones that we use at the left side of the (:) operator.

So we do not need to use an if-then-else at all:

fromDecimal :: Int -> [Int]
fromDecimal 0 = [0]
fromDecimal n = mod n 2 : fromDecimal (div n 2)

Likely this is still not exactly what you want: here we write the binary value such that the last element, is the most significant one. This function will add a tailing zero, which does not make a semantical difference (due to that order), but it is not elegant either.

We can define an function go that omits this zero, if the given value is not zero, like:

fromDecimal :: Int -> [Int]
fromDecimal 0 = [0]
fromDecimal n = go n
    where go 0 = []
          go k = mod k 2 : go (div k 2)

If we however want to write the most significant bit first (so in the same order as we write decimal numbers), then we have to reverse the outcome. We can do this by making use of an accumulator:

fromDecimal :: Int -> [Int]
fromDecimal 0 = [0]
fromDecimal n = go n []
    where go 0 r = r
          go k rs = go (div k 2) (mod k 2:rs)
like image 62
Willem Van Onsem Avatar answered Jan 14 '23 23:01

Willem Van Onsem