Special sum of a list

Learning
1

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!

2

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)
3

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!

4

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
5

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
6

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
7

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

8

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