OCaml：具有不同長度輸入的rippleCarryAdder

Question

如何修改此代碼以接受不同長度的列表？

修改函數rippleCarryAdder以接受不同長度的列表。例如，調用（rippleCarryAdder [true] [false; true]）應該計算爲（[true; false]，false），即1 + 01的計算結果爲2，沒有溢出。

let xor a b = (a || b) && (not (a && b)) 

(* fullAdder : bool -> bool -> bool -> (bool * bool) 
* 
* The call (fullAdder a b carryIn) adds the bits a, b and carryIn 
* producing the sum and the carry out. 
*) 
let fullAdder a b cin = 
    let c = xor a b in 
    let sum = xor c cin in 
    let carryOut = (c && cin) || (a && b) 
    in 
    (sum, carryOut) 

(* rippleCarryAdder : bool list -> bool list -> bool -> (bool list * bool) 
* 
* The call (rippleCarryAdder ms ns carryIn) implements a ripple carry 
* adder. 
*) 
let rippleCarryAdder ms ns = 
    let rec repeat ms ns carryIn acc = 
    match (ms, ns) with 
    | ([], []) -> (acc, carryIn) 
    | (m::ms, n::ns) -> let (sum, carryOut) = fullAdder m n carryIn 
      in 
      repeat ms ns carryOut (sum::acc) 
    in 
    repeat (List.rev ms) (List.rev ns) false [] 

Answer 1

let fill_in a (ms,ns) = 
    let rec fill_left a = function 
     ([],[])   -> [] 
    | ([],_::ns)  -> a::fill_left a ([],ns) 
    | (m::ms,[])  -> m::fill_left a (ms,[]) 
    | (m::ms,_::ns) -> m::fill_left a (ms,ns) 
    in 
    let rec fill_right a = function 
     ([],[])   -> [] 
    | (_::ms,[])  -> a::fill_right a (ms,[]) 
    | ([],n::ns)  -> n::fill_right a ([],ns) 
    | (_::ms,n::ns) -> n::fill_right a (ms,ns) 
    in 
    (fill_left a (ms,ns),fill_right a (ms,ns)) 

let rippleCarryAdder2 ms ns = 
    let (ms,ns)=fill_in false (List.rev ms,List.rev ns) in 
    rippleCarryAdder (List.rev ms) (List.rev ns) 

測試：

# fill_in false ([true;false],[true;false;true;true]);; 
- : bool list * bool list = 
([true; false; false; false], [true; false; true; true]) 

# fill_in 0 ([1;1;0;1],[2;3]);; 
- : int list * int list = ([1; 1; 0; 1], [2; 3; 0; 0]) 

# rippleCarryAdder2 [true] [false;true];; 
- : bool list * bool = ([true; false], false)