Add two numbers stored as a list in F#

Question

I am solving the following problem:

You are given two lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a list.

I wrote the following code:

let addTwoNumbers (a: int list) (b: int list) =
    let rec loop (a: int list) (b: int list) (c: int list) (carry: int) =
        match a, b, carry with
        | (h1::t1), (h2::t2), _ ->
            let q, r = Math.DivRem(h1 + h2 + carry, 10)
            loop t1 t2 (List.append c [r]) q
        | (h1::t1), [], _ ->
            let q, r = Math.DivRem(h1 + carry, 10)
            loop t1 [] (List.append c [r]) q
        | [], (h2::t2), _ ->
            let q, r = Math.DivRem(h2 + carry, 10)
            loop [] t2 (List.append c [r]) q
        | [], [], 0 ->
            c
        | [], [], carry ->
            let q, r = Math.DivRem(carry, 10)
            loop [] [] (List.append c [r]) q
    loop a b [] 0

Is there a way to simplify and possibly to de-duplicate some of this code?

Answer 1

List.append is an expensive O(d) operation, making your addTwoNumbers O(d²). To reverse the list, you would be better off calling List.rev once at the end. (By the way, List.append c [r] would be better written as c @ [r].)

The loop helper function could use a better name. My suggestions are either add or addTwoNumbers'. I don't like the name c either, as it is somewhat mnemonically similar to carry.

Put the base cases first, followed by the recursive cases.

One of the cases can be simplified by taking advantage of commutativity.

When adding two numbers, carry should never be greater than 1.

let addTwoNumbers (a: int list) (b: int list) =
    let rec add (a: int list) (b: int list) (sum: int list) (carry: int) =
        match a, b, carry with
        | [], [], 0 ->
            sum
        | [], [], 1 ->
            1 :: sum
        | [], _, _ ->
            add b a sum carry
        | (h1::t1), [], _ ->
            let c, s = Math.DivRem(h1 + carry, 10)
            add t1 [] (s :: sum) c
        | (h1::t1), (h2::t2), _ ->
            let c, s = Math.DivRem(h1 + h2 + carry, 10)
            add t1 t2 (s :: sum) c
    add a b [] 0 |> List.rev

Answer 2

If your inputs can be adjusted to the same length, prior to calling the function, you can leverage Zip and Fold and simplify the algorithm. (Instead of writing a recursive function and using pattern matching on 5 patterns.)

let addTwoNumbers digits1 digits2 = 

    let carryLast, answer = 
        Seq.zip digits1 digits2
        |>  Seq.fold
                (fun (carry, result) (v1, v2) -> 
                    let div, rem = Math.DivRem ( carry + v1 + v2 , 10)
                    (div, rem :: result)) 
                (0, [])

    if carryLast = 0
        then answer
        else carryLast :: answer