Incomplete pattern matching a tuple in F#

Question

I define a point

type TimeSeriesPoint<'T> = 
    { Time : DateTimeOffset
      Value : 'T }

and a series

type TimeSeries<'T> = TimeSeriesPoint<'T> list

where I assume the points in this list are ordered by time.

I am trying to zip two time series, where, in general, they will have points with the same time, but there might be some points missing in either of them.

Any idea why I get a warning for incomplete pattern matches in the code below?

let zip (series1 : TimeSeries<float>) (series2 : TimeSeries<float>) =
    let rec loop revAcc ser1 ser2 =
       match ser1, ser2 with
       | [], _ | _, [] -> List.rev revAcc
       | hd1::tl1, hd2::tl2 when hd1.Time = hd2.Time ->
           loop ({ Time = hd1.Time; Value = (hd1.Value, hd2.Value) }::revAcc) tl1 tl2
       | hd1::tl1, hd2::tl2 when hd1.Time < hd2.Time ->
           loop revAcc tl1 ser2
       | hd1::tl1, hd2::tl2 when hd1.Time > hd2.Time ->
           loop revAcc ser1 tl2
    loop [] series1 series2

If I write it this way, I get no warning, but is it tail recursive?

let zip' (series1 : TimeSeries<float>) (series2 : TimeSeries<float>) =
    let rec loop revAcc ser1 ser2 =
       match ser1, ser2 with
       | [], _ | _, [] -> List.rev revAcc
       | hd1::tl1, hd2::tl2 ->
           if hd1.Time = hd2.Time then
               loop ({ Time = hd1.Time; Value = (hd1.Value, hd2.Value) }::revAcc) tl1 tl2
           elif hd1.Time < hd2.Time then
               loop revAcc tl1 ser2
           else 
               loop revAcc ser1 tl2
    loop [] series1 series2

Ovoviviparous

I would move the first match at the end and write it as a "catch-all" | _ -> List.rev revAcc – Dowager

Answer 1

In general, it is an anti-pattern to have a when guard in the last pattern.

In zip, you can achieve the same effect as zip' does by removing the redundant guard:

let zip (series1: TimeSeries<float>) (series2: TimeSeries<float>) =
    let rec loop revAcc ser1 ser2 =
       match ser1, ser2 with
       | [], _ | _, [] -> List.rev revAcc
       | hd1::tl1, hd2::tl2 when hd1.Time = hd2.Time ->
           loop ({ Time = hd1.Time; Value = (hd1.Value, hd2.Value) }::revAcc) tl1 tl2
       | hd1::tl1, hd2::tl2 when hd1.Time < hd2.Time ->
           loop revAcc tl1 ser2
       | hd1::tl1, hd2::tl2 ->
           loop revAcc ser1 tl2
    loop [] series1 series2

Both two functions are tail recursive since there is no extra work after a recursive call to loop.

Carltoncarly

Answer 2

For the first case, the compiler just sees the guards and isn't clever enough to reason about when they do / don't apply - you can fix this by removing the last where guard.

For the second I would guess that it is tail recursive, but the best thing to do in these cases is to test with a large input list and see if you don't crash

Weinman

With custom operators, you can make a class such that comparisons return false, for instance how NULL works in SQL. – Skedaddle