Generic higher order function

问题:

Is there a reason why I can use a generic function with different type arguments when I pass it as a local value but not when passed as parameter? For example:

let f = id

let g (x,y) = (f x, f y)

g ( 1, '2')

works fine, but if I try to pass the function as parameter

let g f (x,y) = (f x, f y)

g id ( 1, '2')

it fails because it takes the version f < int > and it tries to apply it twice.

I've found a workaround but it forces me to write twice the function I'm passing:

let g f1 f2 (x,y) = (f1 x, f2 y)

g id id ( 1, '2')

This is the second time I face this problem.

Why it behaves this way, it's not supposed to be the same if the function is a local value or if it's passed as parameter?

Is there a way to do this without duplicating the function?

A hack, maybe using explicit type constraints, inline magic, quotations?

回答1:

Here's the inline magic. Let's take kvb's code and define a single gmap function that handles all cases:

let inline gmap f (x, y) = f $ x, f $ y

type One = One with static member ($) (One, x) = 1  // Example1 ConvertAll
type Id  = Id  with static member ($) (Id , x) = x  // Example2 PassThrough

type SeqSingleton  = SeqSingleton  with static member ($) (SeqSingleton , x) = seq [x]
type ListSingleton = ListSingleton with static member ($) (ListSingleton, x) = [x]
type ListHead      = ListHead      with static member ($) (ListHead, x) = List.head x

// Usage
let pair1 = gmap One ("test", true)
let pair2 = gmap Id  ("test", true)
let pair3 = gmap SeqSingleton  ("test", true)
let pair4 = gmap ListSingleton ("test", true)
let pair5 = gmap ListHead (["test";"test2"], [true;false])

let pair6 = ("test", true) |> gmap ListSingleton |> gmap ListHead

(* results
val pair1 : int * int = (1, 1)
val pair2 : string * bool = ("test", true)
val pair3 : seq<string> * seq<bool> = (["test"], [true])
val pair4 : string list * bool list = (["test"], [true])
val pair5 : string * bool = ("test", true)
val pair6 : string * bool = ("test", true)
*)

UPDATE

It's also possible to use the even more generic gmap function defined here then it will also work with n-uples (n < 9).

回答2:

As rkhayrov mentioned in a comment, type inference is impossible when you can have higher ranked types. In your example, you have

let g f (x,y) = (f x, f y)

Here are two possible types for g which are incompatible (written in a sort of hybrid F#/Haskell syntax):

1. forall 'b,'c,'d. ((forall 'a . 'a -> 'b) -> 'c * 'd -> 'b * 'b)
2. forall 'c, 'd. (forall 'a . 'a -> 'a) -> 'c * 'd -> 'c * 'd)

Given the first type, we could call g (fun x -> 1) ("test", true) and get (1,1). Given the second type, we could call g id ("test", true) and get ("test", true). Neither type is more general than the other.

If you want to use higher ranked types in F#, you can, but you have to be explicit and use an intermediate nominal type. Here's one way to encode each of the possibilities above:

module Example1 = 
    type ConvertAll<'b> =
        abstract Invoke<'a> : 'a -> 'b

    let g (f:ConvertAll<'b>) (x,y) = (f.Invoke x, f.Invoke y)

    //usage
    let pair = g { new ConvertAll<int> with member __.Invoke(x) = 1 } ("test", true)

module Example2 = 
    type PassThrough =
        abstract Invoke<'a> : 'a -> 'a

    let g (f:PassThrough) (x,y) = (f.Invoke x, f.Invoke y)

    //usage
    let pair = g { new PassThrough with member __.Invoke(x) = x } ("test", true)

回答3:

I guess this is the expected behaviour:

In the first case you call two different versions of f (one with int, one with char), in the second case you use the same for both and the compiler infers it (top-bottom, left-right - remember?) to be int->int

The problem is that the generic version will be translated in a concrete one by the compiler. I see no workaround for this - not even with inline but perhaps someone can work some magic here ;)

回答4:

I don't think even inline magic will work here, for example trying

 let inline g f (x:^a,y:^b) = (f x,f y);;

in FSI fails as the compiler infers that ^b must be the same as ^a

Thinking about this, the failure becomes a little more obvious, since we take the function f and apply it to x, it must have a signature like ^a -> 'c, which will fail if we try to apply the function to a element with type ^b.

If you think about this problem though, I can't define a function which takes int->string and expect it to work for char->string without overloads, and you can't pass in the overloads as arguments.

回答5:

The reason for this is that when f is passed as parameter to g then the compiler will try to infer the type of f. Based on the usage of f in the body of function g, the compiler infers that the function is applied to both x and y that means that both x and y parameters has to be of same type and that is the type of the f parameter. In your code example you pass x as integer and that makes the compiler infer that y will also be of type integer.

UPDATE:

You can do something like:

let g (f:obj -> obj) (x : 'a,y : 'b) = (f x :?> 'a ,f y :?> 'b)
g id (1,"1") |> printfn "%A"

The function f need to make sure it returns the same main type that it receives as obj type