More free applicatives!

[treeowl]

The free applicatives I've seen have been based on the binary-operator notion of Applicative. But we can also think in terms of idiom brackets. The simplest one is slow in general:

-- A vinyl record
data Args :: (* -> *) -> [*] -> * where
  Nil :: Args f '[]
  Cons :: f a -> Args f as -> Args f (a ': as)

-- A free Applicative
data Expr f a = forall (ts :: [*]).
      Expr (Args Identity ts -> a) (Args f ts)

It's slow to consume because it will allocate lots of initial segments. That's easily fixed:

data Expr f a = forall (ts :: [*]).
      Expr (forall us. Args Identity (ts ++ us) -> (Args Identity us, a))
               (Args f ts)

It's also slow on construction, of course. I imagine a difference list would do the trick if you don't need reflection.

data Expr f a = forall (ts :: [*]).
      Expr (forall us. Args Identity (ts ++ us) -> (Args Identity us, a))
               (forall us. Args f us -> Args f (ts ++ us))

[treeowl]

@ElvishJerricco's blog post on sorting Traversable containers inspired this, BTW. Using

data Mono x a where
   Mono :: x -> Mono x x

-- Just a length-indexed vector
type List x = Expr (Mono x)

gets you a List x applicative you can traverse with and then sort. Rebuilding the container separately seems much easier than stirring everything together with the standard version. I have no idea if there are other potential applications of the idiom bracket representation, but maybe.