Как добавить два n-битных двоичных целых числа в Haskell?

Question

Как новичок в Haskell, я пытаюсь добавить два n-битных двоичных целых числа.

Ниже приведено то, что я написал на C++, чтобы показать, что я хочу реализовать. Может ли кто-нибудь показать мне, как это сделать в Haskell?

#include <iostream> 
#include <vector> 
#include <deque> 
using namespace std; 
int main() 
{ 
    vector<int> lhs{1,1,1,1}, rhs{1,0,1,1}; 

    //! 3 inputs -> 2 outputs 
    deque<int> sum; 
    int carry = 0; 
    for(auto l = lhs.crbegin(), r = rhs.crbegin(); l != lhs.crend(); ++l, ++r) 
    { 
     int digit_sum = carry + *l + *r; 
     sum.push_front(digit_sum%2); 
     carry = digit_sum/2; 
    } 

    if(carry) 
     sum.push_front(carry); 

    for(auto b : sum) 
     cout << b << " "; 

    return 0; 
} 

выход:

1 1 0 1 0 

Ниже, где я застрял в Haskell ..

add :: (Int, Int, Int) -> (Int, Int) 
add (l,r,c) = (((l+r+c) `mod` 2), ((l+r+c) `div` 2)) 

bAdd :: [Int] -> [Int] -> ([Int], Int) 
bAdd []  []  = ([fst (add (0,0,0))], snd (add(0,0,0))) 
bAdd [l] [r]  = ([fst (add (l,r,0))], snd (add(l,r,0))) 
bAdd (l:lt) (r:rt) = ([fst (add (l,r,add (head)))]) 

Answer 1

Давайте добавим один бит первый.

addWithCarry :: Bool -> Bool -> (Bool, Bool) 
addWithCarry x y = (x /= y, x && y) 
--     "x+y" its carry 

Тогда давайте перейдем к спискам:

-- numbers are represented LSB first e.g. 6 is [False,True,True] 
addBitsWithCarry :: [Bool] -> [Bool] -> Bool -> [Bool] 
-- when we ran out of digits on both args: 
addBitsWithCarry []  []  False = [] 
addBitsWithCarry []  []  True = [True] 
-- when we ran out of digits on one arg, add a zero there: 
addBitsWithCarry a  []  c  = addBitsWithCarry a  [False] c 
addBitsWithCarry []  b  c  = addBitsWithCarry [False] b  c 
-- some digits on both sides 
addBitsWithCarry (x:xs) (y:ys) c  = ??? 
      where (z,c') = addWithCarry ??? 

Вы можете выяснить, что делать в последних строках?

Если вы можете предположить, что ваши номера имеют одинаковую длину бита (как и в коде C++), вы можете удалить две строки над добавлением нулей.

---

Extra подсказка:

-- some digits on both sides 
addBitsWithCarry (x:xs) (y:ys) c  = lsbOfTheSum : restOfTheSum 
      where (z,c') = addWithCarry someBit someOtherBit someCarry 
       lsbOfTheSum = ??? -- what is the first bit (LSB) of the result? 
       restOfTheSum = ??? -- how to compute the other bits (think recursively) 
       someBit  = ??? -- what bit we should add at this step? 
       someOtherBit = ??? -- ... with what other bit? 
       someCarry = ??? -- ... using which carry? 

Если вы понимаете, как работает бинарный сумма, и у вас есть общее представление о Haskell, сопоставления с образцом и рекурсию, вы должны быть в состоянии сделать вывод.