Pattern matching in SML - representing a list as (x::y)

Question

I just started learning functional programming and I find myself very confused by the concept of pattern matching (i'm using SML). Take for example the following expression to insert an element in an ordered list:

fun insert (n,nil) = [n]
  | insert (n, L as x::l) =
    if(n < x) then n::L
    else x::(insert(n,l))

How can the list L be expressed as x::l? I know x refers to the first element of the list and l to the rest, but I don't know what to call this construct or how it can be used. I have read a lot but all the documentation I find doesn't mention this at all. Here is another example that doesn't use the 'as' keyword.

(*returns a list with the sum of each element added of two lists added together*)

fun addLists (nil,L) = L
| addLists (L,nil) = L
| addLists (x::xs,y::ys) =
  (x + y)::(addLists(xs,ys))

Thank you for your help!

Answer 1

For the insert function here:

fun insert (n,nil) = [n]
  | insert (n, L as x::l) =
    if(n < x) then n::L
    else x::(insert(n,l))

The | insert (n, L as x::l) part is a pattern which will be matched against. L as x::l is called an as pattern. It allows us to:

1. Pattern match against a non empty list, where x is the head of the list and l is the tail of the list
2. Refer to the entire matched list x::l with the name L

This is similar (although not totally the same) as doing:

  | insert (n, x::l)

except that if you do that, the insert function will become:

fun insert (n,nil) = [n]
  | insert (n, x::l) =
    if(n < x) then n::x::l
    else x::(insert(n,l))

So the big advantage of using the L as x::l as pattern over a non as pattern is that it allows us to refer to the entire list, not just its head and tail, and avoids an additional list construction when we need to refer to the entire list. Observe that the only difference in the 2 pieces of code is n::L and n::x::l. Since we use the as pattern L as x::l in the first insert function, we are able to do n::L instead of n::x::l. This avoids one :: operation (also known as cons operation).

As for this:

fun addLists (nil,L) = L
| addLists (L,nil) = L
| addLists (x::xs,y::ys) =
  (x + y)::(addLists(xs,ys))

For the second pattern | addLists (x::xs,y::ys), in nowhere do we reconstruct the list x::xs and y::ys in the code following it, so we do not need as patterns. You could write it like:

fun addLists (nil,L) = L
| addLists (L,nil) = L
| addLists (ListX as x::xs, ListY as y::ys) =
  (x + y)::(addLists(xs,ys))

and it'll still work, except that we do not refer to ListX or ListY here, and hence these two as patterns are unnecessary.