Дополнение Дополнения как можно более простое без функций более высокого порядка

Question

Для домашней работы меня попросят реализовать метод дополнения двух в Haskell, который при задании списка чисел в Binary возвращает список дополнений двух из этого списка.

>>>twoComplement [0,0,0,1,1,0,1,0] 
[1,1,1,0,0,1,1,0] 

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

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

Я уже много пробовал. Я понимаю, что мне нужно перевернуть все биты, что не сложно.

flipBits [] = [] 
flipBits (x:xs) 
     |x == 0 = 1:flipBits xs 
     |x == 1 = 0:flipBits xs 
     |otherwise: error "Only 0 and 1 are allowed." 

Но добавление одной части кажется мне очень сложным. Особенно с переносом, если я добавлю 1 к уже существующему 1. Также нельзя использовать генераторы списков. Это все о списках понимания и конкатенаторе :.

Редактировать: С помощью vkuo я написал следующее, что, похоже, хорошо работает до сих пор.

twoComplement:: [Integer] -> [Integer] 
twoComplement [] = [] 
twoComplement lst = turn(tC(turn(lst))) 
       where 
        tC (x:xs) 
         |x == 1 = 1:flipp xs 
         |x == 0 = x:tC xs 
        flipp [] = [] 
        flipp(x:xs) 
         |x == 0 = 1:flipp xs 
         |x == 1 = 0:flipp xs 
        turn [] = [] 
        turn (x:xs) = turn xs ++ [x] 

Если мы хотим использовать reverse, мы должны сделать это сами. Поэтому я сделал это. Интересно, есть ли способ без реверса?

Answer 1

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

Что-то вроде этого:

invAdd :: Int -> (Int,[Int]) -> (Int,[Int]) 
invAdd 0 (0,ds) = (0,1:ds) 
invAdd 0 (1,ds) = (1,0:ds) 
invAdd 1 (0,ds) = (0,0:ds) 
invAdd 1 (1,ds) = (0,1:ds) 

Теперь, если у вас была только одна цифра, то вся операция будет:

twos :: [Int] -> (Int,[Int]) 
twos (d:[]) = invAdd d (1,[]) 

(1,[]) обслуживает для 1 вы должны добавить в addtion к переворачивание бит.

Если у вас есть более чем одну цифры нужна рекурсия вниз

twos (d:ds) = invAdd d (twos ds) 

Это дает вам двоичное дополнение плюс конечный бит переноса. Если вы не хотите, чтобы увидеть кэрри, используйте snd:

*Main> snd (twos [0,0,0,1,1,0,1,0]) 
[1,1,1,0,0,1,1,0] 

Вы можете легко сделать это с BOOLS, а также, так как не используются никакие математические функции и invAdd все случаи явно прописаны.