Polymorphic Type-Directed Function Application
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:
> :set -fplugin=Control.Apply.Unordered.Plugin
> :m + Data.List
> :t intersperse
intersperse :: a -> [a] -> [a]
> intersperse ? "hello" ? ' '
"h e l l o"
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 [Char]
(String
). Digging into the type of intersperse ? "hello"
:
> :t intersperse ? "hello"
intersperse ? "hello"
:: ApplyAtResult
(Data.Type.Nat.FromGHC
(BestParamIxImpl [Char] (Char -> [Char] -> [Char])))
[Char]
(Char -> [Char] -> [Char])
> intersperse ? "hello"
<interactive>:13:1: error:
• No instance for (Show (Char -> [Char]))
...
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