Lambda the Ultimate

I'm looking for example type systems that can type list structure.

For a simple example... (Sorry, I think in code)

// Map two elts at a time, not two lists
def map2(alist:List, f(*,* -> 'u) -> 'u List) // f(*,*) is not good 
  def mklis(nl: 'u List, rest: List)
    match rest
    | a :: b :: r  -> mklis(f(a,b) :: nl, r)  // types of a and b?
    | else -> reverse(nl)
  in mklis(nil, alist);

def plist2alist(plist:List -> <List>List)
  map2(plist, fn(a,b) a :: b :: nil);

plist2alist('(A, 1, B, 2, C, 3))
 => ((A,1),(B,2),(C,3))

It would be very nice to type plist's internal structure, 
thus allowing for typing the map2 function, plist2alist()'s 
resulting internal structure, etc.

I can sort of imagine some kind of regex typing construct, 
but I have no clear ideas on this.  Any languages out there 
do a good job of typing repeating internal patterned structure 
like this?

If this is impossible for any theoretical reason, I'd love 
to know that too :-)

Many thanks.

Scott

I've set up a shared google map, for visualizing the distribution of "birth" places of major programming languages. Please assist by placing a pin in the birth place of major general purpose programming languages. Only place major languages for now, in the sense of wide adoption, rather than intellectual significance please (when the two conflict, of course). That is things like: C, C++, Java, COBOL, Fortran etc.

When in doubt whether a language should be included or as regards the appropriate location to use, please share your thoughts here.