CODEWITHSUNDEEP
ocaml
Alex Yang
Alex Yang

Reputation: 61

Function bigAdd (addition of two int lists)

I need help with the bigAdd, like what exactly I should put for the f base and arg. Big add is supposed take in 2 int arrays and output the sum into another int array like

# bigAdd [9;9] [1;0;0;2];;
- :  int list   =  [1;1;0;1]

# bigAdd [9;9;9;9] [9;9;9];; 
- :  int list  =  [1;0;9;9;8]

I have so far

let rec padZero l1 l2 =
if List.length l1 > List.length l2 then (padZero l1 ([0]@l2))
else if List.length l2 > List.length l1 then (padZero ([0]@l1) l2)
else (l1, l2)

let rec removeZero l = match l with
|[]->
|h::t-> if h == 0 then removeZero t else l

let bigAdd l1 l2 = 
      let add (l1, l2) = 
        let f a x = failwith "to be implemented" in
        let base = failwith "to be implemented" in
        let args = failwith "to be implemented" in
        let (_, res) = List.fold_left f base args in
          res
      in 
        removeZero (add (padZero l1 l2))

Edit: so right now I have

let bigAdd l1 l2 = 
          let add (l1, l2) = 
            let f a x = failwith "to be implemented" in
            let base = 0 in
            let args = List.combine l1 l2 in
            let (_, res) = List.fold_left f base args in
              res
          in 
            removeZero (add (padZero l1 l2)

I'm pretty sure the args is what it's supposed to be, but the base is probably wrong and I have no idea how to write the f. Where exactly does the addition part of the lists come from in this skeleton? Do I convert each in list into an int first and then add them and convert it back to an int list or add them directly and if so how and where in the skeleton.

Can someone describe to me the type f, base, and args will be and what their functions should be? I'm so confused.

Upvotes: 0

Views: 2864

Answers (1)

jrouquie
jrouquie

Reputation: 4415

The point of the question is to understand what the function f a x and the variables base and args should be. This probably isn't your first encounter with List.fold_left, so I'd suggest to review previous exercises with List.fold_left, and add to your question your ideas about the above variables. If you can't come up with any code, explain in English what you understand about them.

You need to understand f first. Once done, you will see clearly what f needs as base and args. To understand f, think about how you would do an addition by hand, digit by digit.

You definitely do not convert the lists to int, the whole point of bigAdd is to handle huge integers, way larger than the maximum int.

Side note about the auxilliary functions:

  • removeZero is good
  • padZero is calling List.length several times, which is slow. You should instead compute the number of zeros to add, then add them all without calling List.length.
  • replace [0]@l1 with 0 :: l1.

Upvotes: 1

Related Questions