Бинарное в десятичное преобразование в Haskell с использованием алгоритма Хорнера - PullRequest
Новая
       63

Бинарное в десятичное преобразование в Haskell с использованием алгоритма Хорнера

0 голосов
/ 05 февраля 2019

Я пытаюсь реализовать функцию, которая берет список Bool, представляющий двоичные числа, такие как [True, False, False], и преобразует его в соответствующее десятичное число в соответствии с методом Хорнера.

Тип функции будет [Bool] -> Int.

Алгоритмы, которыми я следуюю:

Алгоритм Horners Визуальное объяснение:

enter image description here

До сих пор я реализовал логику, в которой сначала говорится, что он проверит, пуст ли список или один элемент в списке [True], даст 1, а [False] даст 0.

Тогда в этом случае binToDecList (x:xs) = binToDecList' x 0 что я сделал для обработки первого элемента, является ли это True или False. 

binToDecList :: [Bool] -> Int
binToDecList []      = error "Empty List"
binToDecList [True]  = 1
binToDecList [False] = 0
binToDecList (x:xs)  =  binToDecList' x 0 
binToDecList' x d | x == True = mul (add d 1)
                  | otherwise = mul (add d 0)

add :: Int -> Int -> Int
add x y = x + y

mul :: Int -> Int
mul x = x * 2

Я хочу использовать результат binToDecList' в следующемитерация вызывает себя рекурсивно для следующего элемента списка.Как я могу сохранить результат, а затем применить его к следующему элементу списка рекурсивно.Любая помощь будет оценена.

1 Ответ

0 голосов
/ 07 февраля 2019

Тип * из foldl говорит нам, как это должно работать. 

foldl :: (b -> a -> b) -> b -> [a] -> b

Ясно [a], третий аргумент, который является спискомчего-то, должен быть список Bool для передачи алгоритму Хорнера.Это означает, что переменная типа a должна быть Bool.

Переменная типа b представляет возможно отдельный тип.Мы пытаемся преобразовать [Bool] в Int, поэтому Int - достойное предположение для b.

foldl работает, просматривая список слева ( т.е. , начиная с его заголовка) и каким-то образом объединяя результат до следующего элемента из списка.Второй аргумент обычно называется z для «нуля» или начального значения для процесса свертывания.Когда foldl достигает конца списка, он возвращает накопленное значение.

Мы можем синтаксически увидеть, что первый аргумент - это некоторая функция, которая выполняет некоторую операцию над элементами типа b и типа aдать b.Теперь функция, которая игнорирует элемент a и безоговорочно приводит к тому, что бы b подходила, но не была бы очень интересной.

Подумайте о том, как работает алгоритм Хорнера.Числа в коленях пути на диаграмме представляют собой условный «результат до сих пор» из предыдущего абзаца.Мы знаем, что b равно Int и a равно Bool, поэтому функция, переданная в foldl, должна преобразовать Bool в Int и объединить ее с результатом.

Первый шаг в алгоритме Хорнера, кажется, является особым случаем, который должен обрабатываться по-разному, но foldl использует одну и ту же функцию на всем протяжении.Если вы представите, что для начала «заполняете насос» невидимым горизонтальным движением (, то есть , умноженное на два), мы можем привести типы в соответствие друг с другом, как кусочки головоломки.Это хорошо, потому что два раза ноль по-прежнему равен нулю.

Таким образом, с точки зрения foldl, алгоритм Хорнера равен 

horners :: [Bool] -> Int
horners = foldl f 0
  where f x b =
          let b' = fromEnum b
          in 2*x + b'

Обратите внимание, что 2*x + b' объединяет последующие горизонтальные и вертикальные перемещения.

Здесь также предлагается, как выразить это в прямой рекурсии. 

horners' :: [Bool] -> Int
horners' [] = 0
horners' l  = go 0 l
  where -- over then down
        go x [] = x
        go x (b:bs) =
          let b' = fromEnum b
          in go (2*x + b') bs

Здесь внутренний цикл go выполняет левый сгиб и объединяет каждый следующий Bool с полученным результатом.в i.

* Педагогическое упрощение: фактический тип обобщает тип списка в Foldable.

...