# Special sum of a list

Hi,
I am trying to sum the squared different of two consecutive elements of a list. Let’s call a function doing this task as sum_sq and then sum_sq [1;2;3] will return (1-2)^2 + (2-3)^2 = 2. Here is my thought:

let sum_sq_2elts x y = match x y with
|x::y -> (x - y) * (x - y)

let rec sum_sqrdiffs sum_sq = match sum_sq with
|x1::x2::[] -> (x1 - x2) * (x1 - x2)
|x::y::z -> sum_sq_2elts x y + sum_sqrdiffs z
I got an error message saying that “Error: This expression has type int list but an expression was expected of type int”. Why is that?

The `sum_sqr_2elts` implementation is wrong. You are doing `x::y` which works only for lists! I think you intended to do:

``let sum_sq_2elts x y = (x-y) * (x-y)``

Hi timmyjose,
I fixed that and I have a new error:
Here is an example of a case that is not matched:
(_::[]|[])
val sum_sqrdiffs : int list -> int =
how can I approach this?
Thanks!

The compiler tells you that your pattern matching is not exhaustive, and is even kind enough to produce examples that are not matched by any condition in `sum_sqrdiffs`. Indeed, you always try to pick the first two elements, so if you use a smaller list as in `sum_sqrdiffs []` or `sum_sqrdiffs `, one can’t decide what to do. You need to either add a general case, as

`````` | _ -> 0
``````

Or you can treat each case separately, if you wish a different behavior for zero or one element. If you add a general case, note that you don’t need your first special case (`x::y::[]`) anymore. Side remark : you can totally use the same names in two separate branches of pattern matching (and should do it if it makes sense), so the first would be more natural as `x::y::[]`.

However there is a related problem with your algorithm. If we execute it on `[1;2;3;4]` then it will proceed as:

1. `sum_sqrdiffs [1;2;3;4]` : Match `x::y::z` with `x=1`,`y=2`,`z=[3;4]`. Return `(1-2)^2 + sum_sqr_diffs [3;4]`
2. `sum_sqr_diffs [3;4]` : Match `x1::x2::[]` with `x1=3`,`x2=4`. Return `(3-4)^2`

You see that you get `(1-2)^2 + (3-4)^2` instead of the expected `(1-2)^2 + (2-3)^2 + (3-4)^2`. The problem is that at each iteration, you indeed need to read the first two elements of the list (the pattern `x::y::z` is correct) but you should not throw both `x` and `y` : `y` will be needed to compute the next square. The fix is to make your recursive call on `y::z` instead of just `z`.

1 Like

You could think about decomposing this into several functions. The core problem is applying a function to adjacent members in a list, which I am trying to capture here:

``````let rec map_pairs f = function
| []        -> failwith "map_pairs"
| [x]       -> failwith "map_pairs"
| [x;y]     -> [f x y]
| x::y::ys  -> f x y :: map_pairs f (y::ys)
``````
2 Likes

To reduce allocations, you may write the last clause like this:

``````x :: (y :: _ as ys) -> f x y :: map_pairs f ys
``````

in that way you don’t need to construct a new list which is structurally equivalent to the tail of your list before recursively call `map_pairs`, you just call it with the tail of the list.

Illustration:

``````let f = function
| [] -> []
| [x] -> [x]
| x :: (y :: _ as ys) -> ys;;
val f : 'a list -> 'a list = <fun>

let g = function
| [] -> []
| [x] -> [x]
| x :: y :: ys -> y :: ys;;
val g : 'a list -> 'a list = <fun>

let l = [1; 2; 3];;
val l : int list = [1; 2; 3]

(* `f l' is physically the same as tail of `l' and not a newly allocated list *)
List.tl l == f l;;
- : bool = true

(* `g l' is a newly allocated list *)
List.tl l == g l;;
- : bool = false
``````

It would be also efficient to write a specialised `fold_left` to avoid creating an intermediate list in the first place.

Yes, for sure. I considered that you gave him the general principle to write such a function, that he can further specialise to its case. I wanted to mention how to avoid unnecessary memory allocations in that kind of pattern matching.

1 Like