How to write a startsWith list function using an Active Pattern instead of when guard?

Question

I need to check if a list starts with another, shorter list. The function, when using when guards is trivial:

let rec startsWith l1 l2 =
  match l1, l2 with
  | [], _ | _, [] -> true
  | x::xs, y::ys when x = y -> startsWith xs ys
  | _ -> false

let lst1 = [ 1; 2; 1 ]
let lst2 = [ 1; 2; 1; 2; 3; ]
let lst3 = [ 1; 3; 1; 2; 3; ]

let c1 = startsWith lst1 lst2  // true
let c2 = startsWith lst1 lst3  // false

But whatever I tried along the lines of an Active Pattern:

let (|HeadsMatch|) (l1 : ('a) list) (l2 : ('a) list) = 
  if l1.Head = l2.Head then Some(l1.Tail, l2.Tail) else None

let rec startsWith l1 l2 =
   match l1, l2 with
   | [], _ | _, [] -> true
   | HeadsMatch /* need to capture the result */ -> startsWith t1 t2
   | _ -> false

I could not make to compile. How to make a version of this function using Active pattern? And if this is not possible, can you explain why?

P.S. Any other nice ways to write the above function?

EDIT: I took the snippet from Daniel's answer to not distract from the real question.

EDIT: My problems started in the beginning. I have defined the active pattern function as

let (|HeadsMatch|_|) lst1 lst2 =

but it should have been

let (|HeadsMatch|_|) (lst1, lst2) =

In which case it would match as in the accepted answer.

Answer 1

I suppose the nicest way might be

let startsWith = Seq.forall2 (=)

If you want to write it from scratch, you need to match on both lists:

let rec startsWith l1 l2 =
  match l1, l2 with
  | [], _ | _, [] -> true
  | x::xs, y::ys when x = y -> startsWith xs ys
  | _ -> false

If you want to write it with an active pattern for learning purposes, using Tarmil's definition it would be

let rec startsWith l1 l2 =
  match l1, l2 with
  | [], _ | _, [] -> true
  | HeadsMatch(xs, ys) -> startsWith xs ys
  | _ -> false

Answer 2

There are two errors in the definition of your active pattern:

1. It's a partial active pattern (since it is possible that it doesn't match) so the syntax is (|HeadsMatch|_|).

2. You need to take the two lists as a pair, since you want to match lst1, lst2.

With these, the code will compile. But it will throw an exception at runtime, because you use .Head and .Tail on lists when you don't know if they have any element; you're not defining the behavior if one of the lists is empty.

Here is an idiomatic implementation of HeadsMatch:

let (|HeadsMatch|_|) (lst1, lst2) =
    match (lst1, lst2) with
    | (x :: xs, y :: ys) when x = y -> Some (xs, ys)
    | _ -> None

Without guard:

let (|HeadsMatch|_|) (lst1, lst2) =
    match (lst1, lst2) with
    | (x :: xs, y :: ys) ->
        if x = y then Some (xs, ys) else None
    | _ -> None

As a side-note, your first implementation has the same problem. The following will throw a runtime exception:

startsWith [1;2] [1]

because you don't check that lst2 is not empty before using .Head and .Tail on it. In general, you should avoid these two methods almost all the time.