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?
Thanks for your input in advance!

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 [1], 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