Как реализовать десятичную двоичную функцию в Haskell - PullRequest
Новая
       35

Как реализовать десятичную двоичную функцию в Haskell

3 голосов
/ 06 февраля 2012

Я реализовал двоичную десятичную функцию в Haskell, и в настоящее время я работаю над функцией, которая преобразует десятичное число в двоичное значение.(Я знаю, что эти функции где-то доступны, хотя они не являются частью Prelude.hs)

Я придумал следующий код для процедурного языка C-типа, но у меня проблемы с его адаптацией вфункциональная парадигма. 

while (n > 0)
{
    if (n % 2 == 1)
        str = str + "1";
    else
        str = str + "0";
    n = n / 2;
}

Я начал заниматься функциональным программированием на Хаскеле совсем недавно, так что я совершенно новичок в функциональном мышлении.Я пытался описать вышеизложенное, используя как рекурсию, так и понимание списка, но я не уверен, как правильно разместить охрану и логику, поскольку это включает в себя несколько условий.Я использую список Int для хранения отдельных двоичных битов. 

--Decimal to binary
toBin:: Int -> [Int]
toBin 0 = [0]
toBin n | (n % 2 == 1) =
        |(n % 2 == 0) =

Я понял, что вышеприведенный шаблон позволит программе выбрать один из вариантов защиты и завершить оценку функции.Я здесь не на том пути?

Ниже приведено то, что я придумал с примитивной рекурсией для преобразования любой базы (меньше 10 вместо 2) в десятичную. 

toDecimal :: [Int] -> Int
toDecimal [] = 0
toDecimal (x:xs) = (x * 2 ^(length xs)) + bin xs

Спасибо заранее.

Ответы [ 4 ]

15 голосов
/ 06 февраля 2012

Нет оператора %;вы, вероятно, ищете `mod` вместо: 

toBin 0 = [0]
toBin n | n `mod` 2 == 1 = ...
        | n `mod` 2 == 0 = ...

Охранники позволяют выбирать между несколькими ветвями функции.В этом случае каждый ... будет результатом toBin n, если его соответствующее условие истинно.Чтобы добавить два списка вместе, вы можете использовать оператор ++, а `div` соответствует целочисленному делению: 

toBin 0 = [0]
toBin n | n `mod` 2 == 1 = toBin (n `div` 2) ++ [1]
        | n `mod` 2 == 0 = toBin (n `div` 2) ++ [0]

Однако с этим есть несколько проблем.Для начала он всегда начинает результат с 0, что является избыточным;кроме того, использование ++ [1] является медленным, поскольку необходимо пройти весь список, чтобы добавить элемент в конец;было бы лучше предварять каждый элемент по ходу, а затем отменить результат в конце.

Чтобы исправить обе эти вещи, мы разделим toBin вверх в основную функцию и вспомогательную функцию: 

toBin 0 = [0]
toBin n = reverse (helper n)

helper 0 = []
helper n | n `mod` 2 == 1 = 1 : helper (n `div` 2)
         | n `mod` 2 == 0 = 0 : helper (n `div` 2)

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

Мы можем упростить код helperполностью пропустив охрану, так как мы просто снова пишем результат n `mod` 2 в правой части: 

helper 0 = []
helper n = (n `mod` 2) : helper (n `div` 2)

Наконец, есть функция, которая выполняет div и mod водин шаг, который может быть более эффективным: 

helper 0 = []
helper n = let (q,r) = n `divMod` 2 in r : helper q

В качестве дополнительного примечания, это на самом деле не преобразует десятичное число в двоичное, оно преобразует целое число в двоичное;Реализации на Haskell вряд ли будут хранить целые числа в десятичном формате, хотя они написаны и напечатаны в этом формате.Чтобы написать полное преобразование десятичного числа в двоичное, потребуется функция, которая анализирует десятичную строку в целое число.

5 голосов
/ 27 апреля 2012 
toBinary :: Int -> [ Int ]

toBinary 0 = [ 0 ]

toBinary n = toBinary ( n `quot` 2 ) ++ [ n `rem` 2 ]
2 голосов
/ 06 февраля 2012 
toBin :: Int -> [Int]
toBin 0 = [0]
toBin 1 = [1]
toBin n
    | n `mod` 2 == 0 = toBin (n `div` 2) ++ [0]
    | otherwise = toBin (n `div` 2) ++ [1]

0 и 1 - тривиальные случаи. если n четное, то вы должны добавить ноль в конец, иначе вы добавите один. Это хорошая практика, чтобы поймать все в вашем последнем защитном выражении (поэтому я использовал иное, что совпадает с True)

0 голосов
/ 03 февраля 2014

Вы можете использовать функцию unfoldr из модуля Data.List и intToDigit из Data.Char: 

dec2bin :: Int -> [Char]
dec2bin = reverse . map intToDigit . unfoldr (\x -> if x==0 then Nothing else Just(rem x 2, div x 2))

Что здесь происходит, это функция unfoldr процессы ввод с предоставленной анонимной функцией до тех пор, пока он не вернет Nothing, при агрегировании первого значения из Just в списке.Этот список содержит Int с, поэтому их необходимо преобразовать в Char с использованием intToDigit, а затем перевернуть, поскольку они собираются в обратном порядке.Список Char s - это строка в Haskell, так что все готово.

...