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:
- Pattern match against a non empty list, where
x
is the head of the list andl
is the tail of the list - Refer to the entire matched list
x::l
with the nameL
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.