Adding 2 Int Lists Together F#

Question

I am working on homework and the problem is where we get 2 int lists of the same size, and then add the numbers together. Example as follows.

    vecadd [1;2;3] [4;5;6];; would return [5;7;9]

I am new to this and I need to keep my code pretty simple so I can learn from it. I have this so far. (Not working)

    let rec vecadd L K =
         if L <> [] then vecadd ((L.Head+K.Head)::L) K else [];;

I essentially want to just replace the first list (L) with the added numbers. Also I have tried to code it a different way using the match cases.

    let rec vecadd L K =
       match L with
         |[]->[]
         |h::[]-> L
         |h::t -> vecadd ((h+K.Head)::[]) K

Neither of them are working and I would appreciate any help I can get.

Answer 1

First, your idea about modifying the first list instead of returning a new one is misguided. Mutation (i.e. modifying data in place) is the number one reason for bugs today (used to be goto, but that's been banned for a long time now). Making every operation produce a new datum rather than modify existing ones is much, much safer. And in some cases it may be even more performant, quite counterintuitively (see below).

Second, the way you're trying to do it, you're not doing what you think you're doing. The double-colon doesn't mean "modify the first item". It means "attach an item in front". For example:

let a = [1; 2; 3]
let b = 4 :: a    // b = [4; 1; 2; 3]
let c = 5 :: b    // c = [5; 4; 1; 2; 3]

That's how lists are actually built: you start with a empty list and prepend items to it. The [1; 2; 3] syntax you're using is just a syntactic sugar for that. That is, [1; 2; 3] === 1::2::3::[].

So how do I modify a list, you ask? The answer is, you don't! F# lists are immutable data structures. Once you've created a list, you can't modify it.

This immutability allows for an interesting optimization. Take another look at the example I posted above, the one with three lists a, b, and c. How many cells of memory do you think these three lists occupy? The first list has 3 items, second - 4, and third - 5, so the total amount of memory taken must be 12, right? Wrong! The total amount of memory taken up by these three lists is actually just 5 cells. This is because list b is not a block of memory of length 4, but rather just the number 4 paired with a pointer to the list a. The number 4 is called "head" of the list, and the pointer is called its "tail". Similarly, the list c consists of one number 5 (its "head") and a pointer to list b, which is its "tail".

If lists were not immutable, one couldn't organize them like this: what if somebody modifies my tail? Lists would have to be copied every time (google "defensive copy").

So the only way to do with lists is to return a new one. What you're trying to do can be described like this: if the input lists are empty, the result is an empty list; otherwise, the result is the sum of tails prepended with the sum of heads. You can write this down in F# almost verbatim:

let rec add a b =
    match a, b with
    | [], [] -> []   // sum of two empty lists is an empty list
    | a::atail, b::btail -> (a + b) :: (add atail btail)  // sum of non-empty lists is sum of their tails prepended with sum of their heads

Note that this program is incomplete: it doesn't specify what the result should be when one input is empty and the other is not. The compiler will generate a warning about this. I'll leave the solution as an exercise for the reader.