The simplest thing in the world. Concatenate two pairs of lists component-wise:
# fun (a, x) (b, y) -> (a @ b, x @ y) ;; - : 'a list * 'b list -> 'a list * 'b list -> 'a list * 'b list = <fun>
Why, let's abstract out the concatenation part and call it thread
, so that it lifts a binary function to operate on pairs component-wise:
# let thread f (a, x) (b, y) = (f a b, f x y) ;; val thread : ('a -> 'b -> 'c) -> 'a * 'a -> 'b * 'b -> 'c * 'c = <fun>
Aaaaaargh! Hindley-Milner doesn't let f
to have different types in different application sites, so it forces both components of each pair to be equal. I'd wish at least for thread
to have the type
val thread : ('a . 'a -> 'a -> 'a) -> 'a * 'b -> 'a * 'b -> 'a * 'b
Is there any way to do this with polymorphic records?
4 comments:
Yes, polymorphic record fields give you such first-class polymorphism:
type binop = { apply: 'a. 'a -> 'a -> 'a }
let thread f (a, x) (b, y) = (f.apply a b, f.apply x y)
Alain,
I tried that, but I stumbled trying to actually build such a binop. I understand that the type of the label apply means "this is a value that, for all 'a, takes an 'a and an 'a and returns an 'a". As far as I can see parametricity dictates that the type is empty. It is here where I think, what am I missing?
I thought that by
val thread : ('a . 'a -> 'a -> 'a) -> 'a * 'b -> 'a * 'b -> 'a * 'b
you actually meant that the first argument had to be polymorphic.
Parametricity does not imply that the type binop is empty. Pure and total functions in this type are (fun x y -> x), (fun x y -> y). But in OCaml, you have many more functions, like min, max, (fun x y -> if Random.int 2 = 0 then x else y), etc...
But it seems that what you really want is a way to pass a "function" that has two unrelated types (like (int list -> int list -> int list) and (string -> string -> string), but not necessarily (int -> int -> int)). What about using a pair of functions?
Like:
let thread (f, g) (a, x) (b, y) = (f a b, g x y)
Hello, it seems no way to do what you want. I'm not able to find original discussion, but some results are summarised at
http://www.petitepomme.net/~schmitta/alan/cwn/2004.12.14.html#3
Post a Comment