# Unordered Function Application In Haskell

Here is a little puzzle: How might a function like
`reorderArgs`

be defined, such that the code below
compiles?

```
{-# LANGUAGE OverloadedStrings #-}
import qualified Data.Text as T
import Control.Apply.Unordered.Mono (reorderArgs)
-- Each example in this group is equal to "hello"
--
-- T.cons :: Char -> T.Text -> T.Text
= T.cons 'h' ello
ex1 = reorderArgs T.cons 'h' ello
ex2 = reorderArgs T.cons ello 'h'
ex3
-- Each example in this group is equal to "hhhello".
--
-- T.justifyRight :: Int -> Char -> T.Text -> T.Text
= T.justifyRight seven 'h' ello
ex4 = reorderArgs T.justifyRight ello 'h' seven
ex5 = reorderArgs T.justifyRight 'h' ello seven
ex6
ello :: T.Text
= "ello"
ello
seven :: Int
= 7 seven
```

I found it quite surprising that this is possible to define. One thing that makes it feasible is a restriction that all arguments are monomorphic. Solving this puzzle is a decent didactic exercise, as it involves a variety of type-level techniques:

Using closed type families to direct instance selection, as described in this post.

Using custom type errors to improve the error messaging, described in the next post.

Using typeclasses to implement polyvariadic functions, described in a subsequent post.

The functionality described in these posts is available on Hackage, in the apply-unordered-mono package. It is also possible to generalize this to polymorphic functions, via a GHC compiler plugin. This is demonstrated by the related apply-unordered package.

## Type-directed application of a single argument

A step towards a solution to this is to write a function which
implements type-directed application of a single argument. Lets name
this function `(?)`

, used like this:

```
appendEllo :: Char -> Text
= T.cons ? ello appendEllo
```

`(?)`

takes any function `f`

, and an argument
`a`

that matches the type of one of its parameters. It will
then partially apply `f`

to this argument. So, the example
above is equivalent to:

```
appendEllo :: Char -> Text
= (\a arg1 -> T.cons arg1 a) ello appendEllo
```

`(?)`

should also be able to provide a value for the first
parameter:

```
prependH :: Text -> Text
= T.cons ? 'h' prependH
```

The plan is to automatically construct this code by using typeclass machinery!

## A failed attempt

One way to approach this might be a typeclass with an associated type family for the result:

```
class ApplyByType a f where
type ApplyByTypeResult a f
?)
( :: f
-> a
-> ApplyByTypeResult a f
```

The type-level algorithm implemented by these instances should check
if the first parameter of `f`

matches `a`

. If it
does, then apply the function:

```
instance ApplyByType a (a -> r) where
type ApplyByTypeResult a (a -> r) = r
? x = f x f
```

If it doesn't, then it should recurse down the right-hand-side of the
`(->)`

type:

```
instance ApplyByType a r => ApplyByType a (b -> r) where
type ApplyByTypeResult a (b -> r) = b -> ApplyByTypeResult a r
? y = \x -> f x ? y f
```

However, this doesn't work! GHC complains:

```
Conflicting family instance declarations:
ApplyByTypeResult a (a -> r) = r
ApplyByTypeResult a (b -> r) = b -> ApplyByTypeResult a r
```

The problem is that open type families do not allow overlap in their instances.

The code that results in this error is didactic/V1.hs on github.

## Attempted fix: use a closed type family

Closed type families permit such overlap, and so provide a nice workaround for this problem. Here's what using a closed type family might look like:

```
type family ApplyByTypeResult a f where
ApplyByTypeResult a (a -> r) = r
ApplyByTypeResult a (b -> r) = b -> ApplyByTypeResult a r
```

This can be tried out in GHCi, by using `:k!`

to ask GHC
to normalize the type – expanding synonyms and applying type
functions:

```
> :k! ApplyByTypeResult Text (Char -> Text -> Text)
ApplyByTypeResult Text (Char -> Text -> Text) :: *
= Char -> Text
```

Awesome! It's figured out that `Text`

matches the second
parameter, and so unordered partial application results in a
`Char -> Text`

type.

Trying it along with the typeclass:

```
class ApplyByType a f where
(?) :: f -> a -> ApplyByTypeResult a f
instance ApplyByType a (a -> r) where
? x = f x
f
instance ApplyByType a r => ApplyByType a (b -> r) where
? y = \x -> f x ? y f
```

Argh! Foiled again:

```
Couldn't match expected type ‘ApplyByTypeResult a (b -> r)’
• type ‘b -> ApplyByTypeResult a r’
with actual The lambda expression ‘\ x -> f x ? y’
•
has one argument,type ‘ApplyByTypeResult a (b -> r)’ has none
but its ...
```

I think the problem here is that GHC has insufficient information to
choose between the different cases of the closed type family. In order
to reject the first equation, it would need to know that `a`

does not unify with `b`

.

The code that results in this error is didactic/V2.hs on github.

## Fix: use a closed type family to choose the instance!

A well-known trick among typeclass machinery enthusiasts is to use a closed type family to choose an instance. Here's how this works:

A type parameter is added to the typeclass, which is used to select the instance.

A

`Proxy`

parameter is added to the method(s), used to specify the type parameter when using the class.A closed type family is used to compute the type to pass in via the

`Proxy`

.

Here's what it looks like for this application:

```
data MatchArgResult
= Matches
| Doesn'tMatch
| NoArgToMatch
type family MatchFirstArg a f :: MatchArgResult where
MatchFirstArg a (a -> r) = 'Matches
MatchFirstArg a (b -> r) = 'Doesn'tMatch
MatchFirstArg _ _ = 'NoArgToMatch
```

The `MatchArgResult`

constructors are used at the
type-level via the `DataKinds`

extension. This is not really
necessary, but it's rather nice for having a proper type-level datatype
to use for the result of the discriminating closed type family.

Trying it out in GHCi:

```
> :k! MatchFirstArg Char (Char -> Text -> Text)
MatchFirstArg Char (Char -> Text -> Text) :: MatchArgResult
= 'Matches
> :k! MatchFirstArg Text (Char -> Text -> Text)
MatchFirstArg Text (Char -> Text -> Text) :: MatchArgResult
= 'Doesn'tMatch
> :k! MatchFirstArg Char Text
MatchFirstArg Char Text :: MatchArgResult
= 'NoArgToMatch
```

It works! When the argument type matches the first parameter, the
result is `Matches`

, and when it does not, the result is
`Doesn'tMatch`

. When it isn't a function at all, the result
is `NoArgToMatch`

.

This closed type family will allow us to choose between
`ApplyByTypeResult`

instances, avoiding any overlap issues.
The method also gets renamed to `applyByTypeImpl`

, as the
`(?)`

function will get defined in terms of it:

```
class ApplyByType (matches :: MatchArgResult) a f where
type ApplyByTypeResult matches a f
applyByTypeImpl :: Proxy matches
-> f
-> a
-> ApplyByTypeResult matches a f
instance ApplyByType 'Matches a (a -> r) where
type ApplyByTypeResult 'Matches a (a -> r) = r
= f x applyByTypeImpl _ f x
```

The recursive case gets a little trickier:

```
instance ApplyByType (MatchFirstArg a r) a r
=> ApplyByType 'Doesn'tMatch a (b -> r) where
type ApplyByTypeResult 'Doesn'tMatch a (b -> r) =
-> ApplyByTypeResult (MatchFirstArg a r) a r
b =
applyByTypeImpl _ f y -> applyByTypeImpl (Proxy :: Proxy (MatchFirstArg a r)) (f x) y \x
```

In 3 different places we need to apply the `MatchFirstArg`

type function in order to discriminate which instance to recurse into.
It might be helpful to reference the old simpler (but non-functioning)
definition:

```
instance ApplyByType a r
=> ApplyByType a (b -> r) where
type ApplyByTypeResult a (b -> r) =
-> ApplyByTypeResult a r
b ? y =
f -> f x ? y \x
```

Giving this new definition a try:

```
Proxy :: Proxy 'Doesn'tMatch) T.cons ("ello" :: T.Text) $ 'h'
λ applyByTypeImpl ("hello"
```

Woohoo! It figured out that `"ello" :: T.Text`

needs to be
passed in as the second argument to `T.cons`

.

However, it's a bit inconvenient to need to pass in that
`Proxy`

. The convenience of `(?)`

can be regained
by writing a helper function which applies
`MatchFirstArg`

:

```
?)
( :: forall matches a f.
~ MatchFirstArg a f
( matches ApplyByType matches a f
,
)=> f -> a -> ApplyByTypeResult matches a f
?) = applyByTypeImpl (Proxy :: Proxy matches) (
```

Giving that a try:

```
> T.cons ? T.pack "ello" ? 'h'
"hello"
```

Boom! Unordered, type-directed function application!

This version of the code is didactic/V3.hs on github. The next post in this series will improve the type errors that occur when the argument type mismatches with all of the parameters.

## Alternative approach: functional dependencies

In the discussion on reddit, u/lightandlight described a more elegant implementation using functional dependencies with overlapping instances:

```
class Apply f x y | f x -> y where
apply :: f -> x -> y
instance {-# overlappable #-} (x ~ (a -> b)) => Apply x a b where
= ($)
apply
instance {-# overlapping #-} Apply b a b' => Apply (a' -> b) a (a' -> b') where
= \a' -> apply (f a') apply f a
```

Very cool! However, this approach leads to more obscure error messages. Lets say we supply the wrong argument type:

```
> cons ? True
<interactive>:1:1: error:
Couldn't match type ‘Text’ with ‘Bool -> b'’
• of ‘?’
arising from a use ...
```

A bit of a head-scratcher! If something like "Inspecting Haskell Instance Resolution" was implemented in GHC, then this error might instead look like:

```
> cons ? True
<interactive>:11:1: error:
Couldn't match type ‘Text’ with ‘Bool -> b'’
• of ‘?
arising from a use Due to the constraint (Text ~ (Bool -> b))
• :
arising from superclass constraintsText ~ (Bool -> b)) =>
(Apply Text Bool b =>
Apply (Text -> Text) Bool (Text -> b) =>
Apply (Char -> Text -> Text) Bool (Char -> Text -> b)
...
```

This makes it a bit clearer that it recursed on the function type and
errored out on attempting to satisfy the `(x ~ (a -> b))`

constraint.

With the implementation here, the error is instead:

```
? True
λ cons
<interactive>:1:1: error:
No instance for (ApplyByType 'NoArgToMatch Bool Text)
• of ‘?’
arising from a use ...
```

Still not great, but I think a bit clearer. The next post describes using GHC custom type errors to further improve this circumstance.

## Appendix: Why?

You might be wondering why you would ever want to use this. Honestly,
I can't think of many practical applications, and so the apply-unordered-mono
package is in the `ACME`

category on Hackage. Even so, I think it's pretty cool that this is
possible.

One potential use-case might be to handle shifting APIs in
dependencies. If a library changes the order of its arguments, you might
be able to use the `(?)`

operator to be compatible with
versions before and after this change, without using the C
preprocessor.

The inspiration for this package was speculation about a programming language where arguments are discriminated by type instead of position. To experiment with this, it turned out to be more straightforward to directly implement the idea in Haskell rather than writing a whole new language. Here are some reasons why I think this is an interesting idea for language design:

Parameter order is often arbitrary, and so requires effort to memorize.

It is safer to have distinct types for all arguments, to avoid bugs due to inadvertent transposition.

Named parameters can help with this, but then you need to memorize the names! Conventions where the name is the same as the type adds verbosity / redundancy.

In practice, many newtypes would be involved in usage of type-directed application. Newtypes might even be associated with the function definition, to provide something akin to named parameters.

Ordered arguments do have some nice advantages, though:

Polymorphism. Matching of arguments with parameters gets ambiguous when type variables are involved.

Ordered arguments provides more direct visual comparison of calls of the same function.

To me, this suggests an alternative implementation approach. Rather than incorporating type-directed application directly into the language, or as a library, it can be part of edit-time tooling. For example, the reformatting tool might handle reordering the arguments.