> you cannot pass it a list of records where all contain the x field of int but some also contain an irrelevant y field and others contain an irrelevant z field.

Yes you can - that's just a existential type. I'm not sure what the syntax would be, but it could be somthing like:

  List (exists a : {x=int, ...'a})

(In practice (ie if your language doesn't support existential types) you might need to jump through hoops like:

  List ((forall a : {x=int, ...'a} -> b) -> b)

or whatever the language-appropriate equivalent is, but in that case your list will have been created with the same hoops, so it's a minor annoyance rather than a serious problem.)