# 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
```