4

It is widely known that Applicative generalises Arrows. In the Idioms are oblivious, arrows are meticulous, monads are promiscuous paper by Sam Lindley, Philip Wadler and Jeremy Yallop it is said that Applicative is equivalent to Static Arrows, that is arrows for which the following isomorphism holds:

arr a b :<->: arr () (a -> b)

As far as I can understand, it could be illustrated the following way:

Note: newtype Identity a = Id { runId :: a }.

Klesli Identity is a Static Arrow as it wraps k :: a -> Identity b. Isomorphism just removes or adds the wrapper.

Kleilsi Maybe is not a Static Arrow as k = Kleisli (const Nothing) exists - all f :: a -> bs correspond to Just . f, and there is no place for k in the isomorphism.

But at the same time both Kleisli Identity and Kleisli Maybe are Arrow instances. Therefore, I can not see how the generalisation works.

In Haskell/Understanding Arrows tutorial on Wikibooks they say static morphism and note the following:

Those two concepts are usually known as static arrows and Kleisli arrows respectively. Since using the word "arrow" with two subtly different meanings would make this text horribly confusing, we opted for "morphism", which is a synonym for this alternative meaning.

That is the only lead I have so far - am I confusing Haskell Arrow and arrows?

So, how does this hierarchy work? How is this Applicative's property formalised/proven?

Zhiltsoff Igor
  • 1,812
  • 8
  • 24
  • It think the confusion is that you can consider `Kleisli Maybe` a static arrow in the appropriate category. `arr a (Maybe b) :<->: arr () (a -> Maybe b)`. – chepner Jul 11 '20 at 14:00
  • @chepner can you, please give an example of a non-static arrow? – Zhiltsoff Igor Jul 11 '20 at 14:47
  • `arr a (f b)` where `f` is not an endofunctor, I think. You can't define an `Arrow` that doesn't use Haskell types, so any functor involved would be an endofunctor on **Hask**. – chepner Jul 11 '20 at 15:13
  • (But I am just guessing, if that's not obvious.) – chepner Jul 11 '20 at 15:15

1 Answers1

3

I believe the word "generalises" is leading you astray. If k is an Arrow, it is indeed the case that:

  • k x for any x will be an Applicative;
  • In particular, k () will be an applicative;
  • That applicative can then be respun as an equivalent static arrow (in terms of Static from semigroupoids, Static (k ()) a b ~ k () (a -> b))

This process, however, is not lossless in the general case: the static arrow Static (k ()) is not necessarily equivalent to the k arrow we started with; there need not be an isomorphism. In other words, static arrows do not generalise arrows. If we were to define a StaticArrow class, it would be a subclass of Arrow, and not a superclass.

P.S.: On the Wikibook quote, the phrasing there is just a matter of emphasis. For instance, while Kleisli arrows are indeed Hughes/Control.Arrow arrows, most of the time when people talk of "Kleisli arrows" they are not thinking about the Arrow instance, but merely about how they are morphisms in a category in which the category laws amount to the monad laws for some monad. In particular, that suffices to frame the discussion in that passage of the Wikibook.

duplode
  • 33,731
  • 7
  • 79
  • 150
  • Thank you for your answer. Truth be told, I am a small bit lost. As far as I know, `Applicative` runs all the effects before the function-in-the-functor is applied to the value-in-the-functor. So, we cannot write a function which gets a line with `getLine`and then prints it back. Yet, `Category` interface allows such a thing. So, how could `StaticArrow` be a subclass of `Category`? And how is this idea of `Applicative` not being able to run effects during the application formalised? – Zhiltsoff Igor Jul 11 '20 at 21:07
  • @ZhiltsoffIgor "Yet, `Category` interface allows such a thing" -- allows, not mandates. Just like there are `Arrow` instances that aren't `ArrowApply` instances (or, for that matter, there are `Category` instances that aren't `Arrow` instances), there are `Arrow` instances that aren't isomorphic to some static arrow, and which therefore wouldn't be an instance of our hypothetical `StaticArrow` class. – duplode Jul 11 '20 at 21:29
  • So the `static arrows -> arrows` on the front page of the "Idioms are oblivious, ..." basically means that any `static arrow` gives rise to an `arrow` without any information being lost? – Zhiltsoff Igor Jul 12 '20 at 05:49
  • Besides, I edited the post a bit - the arrow `t`, as far as I understand, lets us get a line with getLineand then prints it back. That is to do something `Applicative` cannot. `StaticArrow` would inherit this interface. If `StaticArrow` is equivalent to `Applicative`, how should we deal with such computations? Or did I simply assume that `t` does something it does not? – Zhiltsoff Igor Jul 12 '20 at 05:59
  • 1
    [1/2] @ZhiltsoffIgor (1) The left-to-right arrow in the first page diagram means something else, namely, that "there is an equational embedding of static arrows into arrow calculus" (p. 15). Informally, that means an arrow has, at least, all operations of static arrows. Note that the paper also shows that static arrows can be obtained by adding an extra operation to arrows ("classic arrows with delay"); that being so, the fact that adding such an operation actually makes the abstraction weaker might be a little surprising. – duplode Jul 12 '20 at 15:36
  • 1
    [2/2] @ZhiltsoffIgor (2) On your edit: `arr` can lift arbitrary functions to an arrow, so using it in that way doesn't tell us much about what arrow composition itself allows. One of the arrow laws is `arr (g . f) = arr g <<< arr f`, which means your `t` amounts to `arr (const (getLine >>= print))`, and so the arrow isn't actually handling the `IO` effects. Contrast that with, for instance, `Kleisli (const getLine) >>> Kleisli print :: Kleisli IO a ()`, in which the sequencing of effects is actually being done through `(>>>)`. – duplode Jul 12 '20 at 15:47