Between Applicative Functor and Monad

Question

Is it possible to design an Applicative Functor with a few extra stack manipulation functions push, pop, and a specialized branching function ifA :: forall a. f Boolean -> f a -> f a -> f a, and achieve a model for computation that is equal in expressive power to a Monad? (Can express any program that a Monad can express).

Such a model could be useful for representing computation and maintaining full static analysis.

Such an Applicative Functor might need to be dependently typed (Index Applicative Functor?) with a heterogeneous list. So that it can keep type-safety for push and pop.

It must be possible somehow. Because a effectful forth program can be viewed as a Monoid.

Answer 1

tl;dr I believe static ArrowChoice is what you're looking for.

---

To elaborate on your interesting question: If we want to have branching computations, we need to be able to pass outputs of one computation as inputs to the following ones.

For Applicatives effects can't depend on results, we can imagine that first we perform all effects and then combine all results using a pure computation. Therefore we can represent such a computation with input i, output o and effect m as m (i -> o).

For Monads effects can fully depend on inputs. Thus we can represent computations as i -> m o.

If we want to get somewhere in between, we need to parametrise our computations both in input and output. And this is how we get to Arrows, which span the space between Applicatives and Monads.

Just like each monad, each arrow a gives raise to an Applicative. If we fix the input, we can combine two arrows a i o1 and a i o2 using &&& (and then map the pure part of the result with >>> and arr).

On the other hand, from each applicative f we can define an arrow as f (i -> o). This is the weakest kind of an arrow - it's power is equivalent just to f. Such arrows are called static arrows and can be recognized by having an isomorphism between a i o and a () (i -> o) (while we have a () (i -> o) -> a i o for any arrow, the opposite exists just for static ones). In other words, the internal effect of the arrow doesn't depend on its input.

At the other end of the spectrum we have Kleisli arrows. For any monad we can construct arrow i -> m o, whose power is equivalent to the monad.

The interesting part is that we can have arrows in between Monad and Applicative. An nice example, which was the motivation for inventing arrows, is the combination of a static and dynamic parsers¸ The parser has a static part that determines the set of characters the parser is able to consume next, and this static part is computed without having to run the arrow.

---

I guess your idea is to have

ifA :: forall a. f Boolean -> f a -> f a -> f a

and to pass values to branched computations using stack operations. I'd say that for functional settings it's more natural to embed values into branching. Indeed, the closest operation in ArrowChoice (which describes computations that can branch) is

(|||) :: a b d -> a c d -> a (Either b c) d 

---

There is even more general concept - generalized arrows. It allows to represent computations that aren't a superset of Haskell (in Arrow we can embed any pure function using arr), such as bi-directional circuits that can be used for both parsing and pretty-printing.