Here's a little puzzle: find an applicative transformer that keeps (<*>) associated to the left. So if you write x <*> (y <*> z) it should simplify to something like ((\f g h -> f (g h)) <$> x <*> y) <*> z (and you can see here that getting the types to line up can get pretty tricky).
For a related example, the Cont and Codensity monad transformers keep (>>=) associated to the right. (Note that for applicatives, unlike monads, the "left-" and "right-leaning" variants of the problem are symmetrical if you also replace (<*>) with a flipped version.)
One idea is to look for a free applicative, but the three variants in the free library are not ideal. Two are recursive data structures, so that prevents inlining (if not for that, they would probably be okay). The third doesn't reassociate anything.
I have a working solution (and I'd be happy to talk about it), but is there anything simpler than this? or is it somehow necessary to reach for (rank 2, order 4)-functions?
I am more specifically interested in the problem using (<*>) rather than liftA2, but it's also cool to think about the liftA2 variant.
It's also important to not freely insert (<$>).
For those wondering, I need this for generic deriving of Traversable instances that simpify to Core terms identical to what's produced by the DeriveTraversable extension. It's not strictly necessary to do it with a "left-leaning applicative", but I'm posing this as a fun little problem of its own.
@Lysxia Interesting question. I'm not following what it means to have an applicative transformer. How should the output applicative be related to the input applicative? Is it supposed to be the free applicative generated by the input functor?
I haven't thought about it very carefully but as a random thought, given a notion of forgetful higher order functor that does nothing, those look very much like a counit/unit pair
I don't have an answer yet, but I do have another question that might be helpful. Can we define a "semigroup transformer" that, given a semigroup, produces another semigroup in which all the appends are left associated?
I'm just talking about semigroups to break it into more compositions of free things, but we can go straight to the monoid if it helps us not worry about nonempty
The basic idea i'm thinking about is that the primary function of an applicative is to cohere a semigroup in its codomain with a transported semigroup from its domain
I'm confusing myself at this point, but maybe this does something :sweat_smile:
data Day f g a = forall x y. Day ((x, y) -> a) (f x) (g y)
newtype FA f a = FA { runFA :: (Identity :+: Day f (FreeApplicative f)) a }
newtype Hom f g a = Hom (forall r. f (a -> r) -> g r)
newtype DFA f a = DFA { runDFA :: Hom (FA f) (FA f) a }
it's probably impossible in Haskell, but I'm wondering if at least conceptually a "flat" encoding like this makes any sense:
-- probably actually need a class heretypefamilyNAry(xs::[*])(r::*)::*whereNAry[]r=rNAry(x:xs)r=x->NAryxsrtypefamilyZipWith(f::x->y->z)(xs::[x])(ys::[y])::[z]where...dataNDay(fs::[*->*])a=forall(xs::[*]).NDay(NAryxsa)(HList(ZipWithApplyfsxs))dataFreeApplicativefa=forall(fs::[*->*]).All(~f)fs=>FreeApplicative(NDayfsa)
dataCayleyfa=Cayley(forallr.f(a->r)->fr)fromCayley::forallf.Applicativef=>Cayleyf~>ffromCayley(Cayleyf)=f(pureidentity)toCayley::forallf.Applicativef=>f~>CayleyftoCayleyfa=Cayley(\far->(\aar->ara)<$>fa<*>far)pureCayley::forallfa.Applicativef=>a->CayleyfapureCayleya=Cayley(\far->(\ar->ara)<$>far)applyCayley::forallfab.Applicativef=>Cayleyf(a->b)->Cayleyfa->CayleyfbapplyCayley(Cayleyf)(Cayleyg)=Cayley\h->-- f :: f ((a -> b) -> r) -> f r -- takes a, gives b-- g :: f (a -> r) -> f r -- gives a-- h :: f (b -> r) -- takes b-- map (\br a ab -> br (ab a)) h :: f (a -> (a -> b) -> r)-- g :: f (a -> (a -> b) -> r) -> f ((a -> b) -> r)-- f . g :: f (a -> (a -> b) -> r) -> f r-- f . g $ h :: f rf(g((\braab->br(aba))<$>h))
Why is the extra fmap a problem? I think it might be unavoidable …
It's not unavoidable, as I said I already have a working solution, I'm looking for a simpler version, or, as I think we're doing now, getting it out of a more general construction.
fmap generally has a runtime cost, and it gets in the way of inspection testing. Ensuring that the Core that GHC spits out is the same as a hand-tuned program gives very strong performance guarantees.
There are some tricks with typeclasses to get things to unfold (by somehow not having value-level recursion). I think if you do that, it will simplify the HList away to some Church encoding or other lambda-calculus-based encoding.
Here's a little puzzle: find an applicative transformer that keeps
(<*>)
associated to the left. So if you writex <*> (y <*> z)
it should simplify to something like((\f g h -> f (g h)) <$> x <*> y) <*> z
(and you can see here that getting the types to line up can get pretty tricky).For a related example, the
Cont
andCodensity
monad transformers keep(>>=)
associated to the right. (Note that for applicatives, unlike monads, the "left-" and "right-leaning" variants of the problem are symmetrical if you also replace(<*>)
with a flipped version.)One idea is to look for a free applicative, but the three variants in the free library are not ideal. Two are recursive data structures, so that prevents inlining (if not for that, they would probably be okay). The third doesn't reassociate anything.
I have a working solution (and I'd be happy to talk about it), but is there anything simpler than this? or is it somehow necessary to reach for (rank 2, order 4)-functions?
Some remarks:
(<*>)
rather thanliftA2
, but it's also cool to think about theliftA2
variant.(<$>)
.Traversable
instances that simpify to Core terms identical to what's produced by theDeriveTraversable
extension. It's not strictly necessary to do it with a "left-leaning applicative", but I'm posing this as a fun little problem of its own.@Lysxia Interesting question. I'm not following what it means to have an applicative transformer. How should the output applicative be related to the input applicative? Is it supposed to be the free applicative generated by the input functor?
For example what prevents the silly choice of just ignoring the input applicative and constantly producing some arbitrary left associated applicative?
Good question! I think any solution would probably hide a free applicative somewhere, but it's not necessary to frame the problem in those terms.
The requirement is that you can wrap any applicative with that transformer, combine stuff in the wrapped applicative, and then unwrap it at the end.
fromAp . toAp = id
plus some homomorphism laws.I haven't thought about it very carefully but as a random thought, given a notion of forgetful higher order functor that does nothing, those look very much like a counit/unit pair
Oh, I hadn't thought about it this way! That probably has to do with the fact that free constructions are monads :)
I can provide some inspection tests if you want to know whether a solution fits the bill
yes please
I’m not following this part:
How would you build a free applicative without recursive data structures?
With a final encoding like https://hackage.haskell.org/package/free-5.1.3/docs/Control-Applicative-Free-Final.html
Ah
But that doesn’t allow any inspection
I don't have an answer yet, but I do have another question that might be helpful. Can we define a "semigroup transformer" that, given a semigroup, produces another semigroup in which all the appends are left associated?
I believe difference lists are relevant to this question
inspection may be one way to do it, but it is not necessary to solve the problem
@Asad Saeeduddin yeah that's what difference lists do!
you might need a bit of fiddling for the nonempty requirement
in fact that's basically how my current solution works
I'm just talking about semigroups to break it into more compositions of free things, but we can go straight to the monoid if it helps us not worry about nonempty
The basic idea i'm thinking about is that the primary function of an applicative is to cohere a semigroup in its codomain with a transported semigroup from its domain
We already have the Cayley trick for reassociating monoids, so maybe we can directly apply that somehow
This has left and right associative (rescursive) free constructions: https://arxiv.org/pdf/1403.0749.pdf
If the solution just falls out of Cayley's theorem that would be great :)
Here is the "listy" free monoid encoding of a free applicative:
I wonder if we can do Cayley-fication of monoid objects in arbitrary (closed?) monoidal categories
the Day convolution monoidal structure is closed, so I suspect the internal arrow gives us a way to "difference listify" this monoid
Yeah, "Notions of computation as monoids" probably covers this
As in https://pursuit.purescript.org/packages/purescript-day/10.0.1/docs/Data.Functor.Day.Hom#t:Hom ? Probably would plug in
pure identity
forf (a -> r)
...@Nicholas Scheel Right. Does the associativity then maybe come down to how composition of that internal hom is defined?
I think so ...
I'm confusing myself at this point, but maybe this does something :sweat_smile:
Those purescript instanes for
Hom
look really weird because they requireMonad
andComonad
instancesYeah, we're not interested in those.
I see, that doesn't matter for the Cayley representation (
Hom f f
)Looking at this (p22, section 5.4) https://arxiv.org/pdf/1406.4823.pdf the
Applicative
instance inserts somefmap
, which is a problem for me.it's probably impossible in Haskell, but I'm wondering if at least conceptually a "flat" encoding like this makes any sense:
Here's what I have so far:
Why is the extra fmap a problem? I think it might be unavoidable …
It's not unavoidable, as I said I already have a working solution, I'm looking for a simpler version, or, as I think we're doing now, getting it out of a more general construction.
Note: I haven't figured out which way this associates!
I think the HList version would have no fmaps
or at least no fmaps in the functor in question
I'm going to give it a shot in Agda
Oh, I see, you just deferred the
fmap
in your version. I guess it's otherwise equivalent to mine.fmap
generally has a runtime cost, and it gets in the way of inspection testing. Ensuring that the Core that GHC spits out is the same as a hand-tuned program gives very strong performance guarantees.Is that Yoneda?
forall u. ((a -> r) -> u) -> f u ~ f (a -> r)
yup
So Yoneda Cayley … probably the most general construction there is :shrug:
@Asad Saeeduddin that would work yeah, just
HList
is another recursive structure.@Lysxia It doesn't have to be. With dependent products, you can represent it as a function I think
also the recursion can be in either direction if you do write it as a recursive datatype
or even be "branching" instead of completely leaning in one direction for whatever reason if you expend enough effort
fwiw I have some Dhall code to generate traversable instances :wink: https://github.com/MonoidMusician/dhall-purescript/blob/master/src/Dhall/Core/AST/Types/gen.dhall#L581
@Lysxia Isn't it possible even in Haskell for application of an nary function to an hlist to be completely inlined when the type level list is known?
If you write a recursive function it just won't be inlined.
There are some tricks with typeclasses to get things to unfold (by somehow not having value-level recursion). I think if you do that, it will simplify the
HList
away to some Church encoding or other lambda-calculus-based encoding.There's an example of "unfolding recursive functions" at the very end of this post (
class Sum
): https://mpickering.github.io/posts/2017-03-20-inlining-and-specialisation.htmlThere's a lot more we can keep discussing about here, but thanks @Asad Saeeduddin and @Nicholas Scheel for putting me on the track of Cayley+Yoneda!