Haskell Десятичный в двоичный

Question

Я пытаюсь создать функцию, которая преобразует десятичное число (Int) в двоичное число. К сожалению, кроме как в Java, в Haskell невозможно разделить int на два. Я очень плохо знаком с функциональным программированием, поэтому проблема может быть чем-то тривиальным. До сих пор я не мог найти другое решение этой проблемы, но вот моя первая попытка:

 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) 

Я получил реализацию Java, которую я делал раньше:

   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;
        }       }
}

Надеюсь, это поможет найти решение!

Answer 1

Двоичные числа обычно являются строками и в действительности не используются в вычислениях. Строки также менее сложны.

Шаблон двоичных чисел такой же, как и любой другой. Это повторяется, но быстрее. Только небольшой набор необходим для генерации до 256 (0-255) двоичных чисел. Шаблон может систематически расширяться для большего. Стартовый шаблон 4, 0-3

bd = ["00","01","10","11"]

Функция объединения их в большие числа:

d2b n = head.drop n $ [ d++e++f++g | d <- bd, e <- bd, f <- bd, g <- bd]

d2b 125

"01111101"

Если не понятно, как расширяться, то

bd = ["000","001","010","011","100","101","110","111"]

Даст вам до 4096 двоичных цифр (0-4095). Все остальное остается прежним.

Если это не очевидно, функция db2 использует 4 пары двоичных чисел, поэтому 4 из набора. (2 ^ 8) - 1 или (2 ^ 12) - 1 - это сколько вы получаете.

Кстати, списком для понимания являются do структуры с сахарным покрытием.

Создайте вышеуказанные шаблоны с

[ a++b | a <- ["0","1"], b <- ["0","1"] ]

[ "00", "01", "10", "11"]

и

[ a++b++c | a <- ["0","1"], b <- ["0","1"], c <- ["0","1"] ]

* 1 029 * [ "000", "001", "010", "011", "100", "101", "110", "111"]

В целом, один шаблон и одна функция могут служить цели

b2 = ["0","1"]
b4 = [ a++b++c++d | a <- b2, b <- b2, c <- b2, d <- b2]
b4

[ "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011 », "1100", "1101", "1110", "1111"] * 1 035 *

bb n = head.drop n $ [ a++b++c++d | a <- b4, b <- b4, c <- b4, d <- b4]
bb 32768

"1000000000000000"

bb 65535

"1111111111111111"

Для вычисления двоичного числа из десятичного числа непосредственно в Haskell с использованием вычитания

cvtd n (x:xs) | x>n  = 0:(cvtd  n xs)
              | n>x  = 1:(cvtd (n-x) xs)
              | True = 1:[0|f<-xs]

Используйте любое количество битов, которое вы хотите, например, 10 бит.

cvtd 639 [2^e|e<-[9,8..0]]

[1,0,0,1,1,1,1,1,1,1]

Answer 2

Вы не можете / целых чисел в Haskell - деление не определено в терминах целых чисел!Для интегрального деления используйте функцию div, но в вашем случае более подходящим будет divMod, который поставляется с mod безвозмездно.

Кроме того, вы получите обратный вывод, так что вы можете reverseзатем вручную или используйте более эффективную для памяти версию с аккумулятором:

decToBin :: Int -> [Int]
decToBin = go [] where
   go acc 0 = acc
   go acc n = let (d, m) = n `divMod` 2 in go (m : acc) d

go даст пустой список для 0.Вы можете добавить его вручную, если список пуст:

decToBin = (\l -> if null l then [0] else l) . go [] where ...

Answer 3

Продумайте, как будет работать ваш алгоритм.Он начинается с 2⁰, поэтому он будет генерировать биты в обратном направлении по сравнению с тем, как мы обычно о них думаем, то есть наименее значимый бит первым.Ваш алгоритм может представлять только неотрицательные двоичные целые числа.

fromDecimal :: Int -> [Int]
fromDecimal d | d < 0     = error "Must be non-negative"
              | d == 0    = [0]
              | otherwise = reverse (go d)
  where go 0 = []
        go d = d `rem` 2 : go (d `div` 2)

В Haskell, когда мы генерируем список в обратном порядке, продолжайте и делайте это, но затем reverse результат в конце.Причина этого заключается в том, что составление списка (склеивание новых элементов в заголовке с помощью :) имеет постоянную стоимость, а reverse в конце имеет линейную стоимость, но добавление с ++ имеет квадратичную стоимость.

Обычный стиль Haskell состоит в том, чтобы иметь частный внутренний цикл с именем go, который применяется внешней функцией, когда он доволен своими аргументами.Базовый случай должен заканчиваться пустым списком, когда d достигает нуля.В противном случае мы берем текущий остаток по модулю 2, а затем продолжаем с d, разделенного пополам и усеченными.

Без специального случая для нуля, fromDecimal 0 будет пустым списком, а не [0].

Answer 4

Есть некоторые проблемы с вашим решением. Прежде всего, я советую не использовать do на всех , пока вы не поймете, что делает do. Здесь нам вообще не нужно do.

К сожалению, кроме как в Java, в haskell невозможно разделить int на два.

На самом деле, но оператор / (который на самом деле является функцией (/)) имеет тип (/) :: Fractional a => a -> a -> a. Int не является Fractional. Вы можете выполнить целочисленное деление с помощью div :: Integral a => a -> a -> a.

Итак, код выглядит так:

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

Но мы определенно можем сделать это более элегантным. mod n 2 может привести только к двум результатам: 0 и 1, и именно эти мы используем слева от оператора (:).

Так что нам вообще не нужно использовать if - then - else:

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

Вероятно, это все еще не совсем то, что вы хотите: здесь мы записываем двоичное значение таким образом, что последний элемент является наиболее значимым. Эта функция добавит tailing zero, который не имеет семантической разницы (из-за этого порядка), но также не элегантен.

Мы можем определить функцию go, которая пропускает этот ноль, если заданное значение не равно нулю, например:

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

Однако если мы сначала хотим записать старший значащий бит (в том же порядке, в котором мы записываем десятичные числа), то мы должны изменить результат на обратный. Мы можем сделать это, используя аккумулятор :

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)