In "Unordered Function Application In Haskell", I described an approach to implementing unordered function application in Haskell. This approach only works for monomorphic functions and arguments. Happily, I found a solution to this issue! The goal of this post is just to sketch the solution, not describe it in detail. For more detail, see the code.
The solution: GHC plugin & -XOverlappingInstances logic
Matching arguments to parameters becomes quite ambiguous, so some concept of a "best fit" for an argument needs to be defined. As far as I know, there is no way for type families to work on types generically, and so a general purpose "best-fit" type family cannot be defined.
The solution I ended up with is to write a GHC plugin which substitutes uses of a type family with a
Nat indicating which parameter is the "best fit" for the argument.
The idea is to use the same logic as
-XOverlappingInstances when determining which parameter is the "best fit" for the argument. In essence,
-XOverlappingInstances will select the instance where more of the type's structure matches. The code in the plugin for determining the most specific parameter is directly copy-modified from the code in GHC for selecting an overlapping instance.
Here's what it looks like to use this package, via running
stack GHCi apply-unordered in the apply-unordered repository:
Whoah! The arguments are provided in swapped order to a polymorphic function, and it worked! For
intersperse ? "hello", it decided to provide "hello" as the second argument, because
[a] is the more specific match for
String). Digging into the type of
intersperse ? "hello":
As expected, the normalized type is
Char -> [Char]. The unnormalized type is more more complicated, and involves an
ApplyAtResult type family and a
BestParamIxImpl type family. The GHC plugin magically replaces
BestParamIxImpl type family with a type-level integer indicating the parameter index the argument should be applied to.
This approach, a plugin which replaces the type family, was based on an approach copy-modified from Sandy Maguire's magic-tyfams package.
ApplyAt type-class machinery is then used to generate the code which plumbs the argument to the parameter. This is similar to
ApplyByType, but directed by a
Nat rather than checking for matching types. Here is how this machinery is defined:
-- | Typeclass used to implement 'applyN'. The first type argument is -- the number of arguments to skip before doing the application. class ApplyAt (n :: Nat) a f where type ApplyAtResult n a f applyAtImpl :: Proxy n -> f -> a -> ApplyAtResult n a f instance a ~ b => ApplyAt Z a (b -> r) where type ApplyAtResult Z a (b -> r) = r applyAtImpl _ f x = f x instance ApplyAt n a r => ApplyAt (S n) a (b -> r) where type ApplyAtResult (S n) a (b -> r) = b -> ApplyAtResult n a r applyAtImpl _ f y = \x -> applyAtImpl (Proxy :: Proxy n) (f x) y