在OCaml中添加兩個列表

Question

假設我們使用一個列表來反向表示數字，每個節點都是數字中的一個數字。

所以[1;2;3;4;5]是數54321

現在我們要添加了兩個這樣的列表，例如，添加[1; 2]和[3; 4]，我們得到[4; 6]，這是數64

---

這裏是我的代碼：

let add l1 l2 = 
    let rec add_to up acc = function 
    | [] -> if up = 1 then 1::acc else acc 
    | hd::tl -> 
     let s = hd+up in 
     if s >= 10 then add_to 1 ((s-10)::acc) tl 
     else List.rev_append tl (s::acc) 
    and 
    add_up up acc = function 
    | [], [] -> if up = 1 then 1::acc else acc 
    | l, [] | [], l -> (add_to up [] l) @ acc 
    | hd1::tl1, hd2::tl2 -> 
     let s = hd1+hd2+up in 
     if s >= 10 then add_up 1 ((s-10)::acc) (tl1, tl2) 
     else add_up 0 (s::acc) (tl1, tl2) 
    in 
    List.rev (add_up 0 [] (l1, l2)) 

的想法很簡單，只是從兩個列表添加兩個HDS，並攜帶1到下一如果兩個HDS的總和是更大或相等與10.

但是，我認爲我的代碼看起來不漂亮。

1. 我們有解決進位的邏輯的冗餘部分。
2. 我必須在兩個列表上做@。

任何人都可以幫助我使它更美麗？

Answer 1

我認爲訣竅是推廣。本質是增加三件事，而不是兩件。

let sum a b = 
    let rec isum a b c = 
     match a, b with 
     | [], [] -> if c = 0 then [] else [c] 
     | [], x | x, [] -> isum [0] x c 
     | ah :: at, bh :: bt -> 
      let s = ah + bh + c in 
      (s mod 10) :: isum at bt (s/10) 
    in 
    isum a b 0 

此代碼不是尾遞歸。尾遞歸版本會稍微不太優雅。

注：我假設你使用[]來表示0