0

Assume we use a list to represent number reversely, each node is a digit inside the number.

So [1;2;3;4;5] is the number 54321

Now we want to add up two such lists, e.g., adding [1;2] and [3;4], we get [4;6], which is the number 64.

here is my code:

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))

The idea is very simple, just add two hds from two lists, and carry 1 to the next if the sum of two hds are bigger or equal with 10.

However, I think my code does not look beautiful.

  1. we have the redundant part of the logic to solve the carry.
  2. I have to do @ on two lists.

Anyone can help me to make it more beautiful?

Ferruccio
  • 98,941
  • 38
  • 226
  • 299
Jackson Tale
  • 25,428
  • 34
  • 149
  • 271

1 Answers1

1

I think the trick is to generalize. The essence is to add three things, not two.

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

This code isn't tail recursive. A tail recursive version will be a little less elegant.

Note: I assume you use [] to represent 0.

Jeffrey Scofield
  • 65,646
  • 2
  • 72
  • 108