реверса двоичных чисел в Haskell

Question

Я определил тип данных для двоичных чисел следующего

data Bin = Nil | O Bin | I Bin 
      deriving (Show, Eq) 

я хочу, чтобы определить функцию reverse :: Bin -> Bin так, что, когда я внести свой вклад как

reverse (I (O (I (I Nil)))) я должен получить outut I (I (O (I Nil))), что означает обратный как вход, любое тело, пожалуйста, дайте мне подсказку, как я могу это сделать?

Answer 1

Почему вы так делаете? Почему не что-то вроде этого:

data Bit = I | O 
newtype Bin = List Bit 

Тогда вы могли бы просто использовать обратную операцию прелюдии непосредственно ...

Редактировать Простая подстановка из функции Prelude в:

reverse x = rev x [] 
    where 
    rev [] a = a 
    rev (x:xs) a = rev xs (x:a) 

дает :

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) 

Дело в том, ваш тип очень похож на тип списка:

data List a = a : (List a) | [] 

поэтому логика для списка подпрограмм относится непосредственно к вашему типу.

Answer 2

List модуля GHC определяет функцию reverse в списках, как это:

reverse l = rev l [] 
    where 
    rev []  a = a 
    rev (x:xs) a = rev xs (x:a) 

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

Этот же принцип может применяться к вашему двоичному типу номера, чтобы изменить порядок цифр.

Answer 3

Кажется странным, что вы определяете тип списка и тип битов. Я думаю, что я бы повторно использовал список базовых библиотек типа [] и просто установил элементы в качестве вашего битового типа, как показано выше в Aidan.

Answer 4

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 

Answer 5

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 

Answer 6

это возможное решение:

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)