You can determine a lot more about a computation described only in terms of an applicative functor as you can from a monadic one, without running any of its effects (i.e. "statically").
gergoerdi covered analysis, but composition is simple. For any two Applicatives F and G and value type A the following 4 values are all Applicative values
F A
G A
F (G A)
G (F A)
But for monads only the first two are monads for general monads F and G. So, Applicatives compose better!
Even for monad transformers it's not necessarily the case that direct composition leads to a monad. For instance, ContT looks like
newtype ContT r m a = ContT ((a -> m r) -> m r)
so ContT M A is not the same as Cont (M A).
Monads also compose under products as two parallel monadic computations
data (f * g) a = Pair (f a) (g a)
p1 :: (f * g) a -> f a
p1 (Pair fa _) = fa
p2 :: (f * g) a -> g a
p2 (Pair _ ga) = ga
instance (Monad f, Monad g) => Monad (f * g) where
return a = Pair (return a) (return a)
Pair fa ga >>= k = Pair (fa >>= p1 . k) (ga >>= p2 . k)
You can also talk about composition under sums
data (f + g) a = Inl (f a) | Inr (g a)
and you'll get compositions of applicatives here so long as you have a notion of natural transformation
class Natural f g where
phi :: f a -> g a
instance (Applicative f, Applicative g, Natural f g) => Applicative (f + g) where
pure a = Inl (pure a)
Inl ff <*> Inl fa = Inl ( ff <*> fa)
Inr gf <*> Inr ga = Inr ( gf <*> ga)
Inl ff <*> Inr ga = Inr (phi ff <*> ga)
Inr gf <*> Inl fa = Inr ( gf <*> phi fa)
but there's no way to get a similar monad. It turns out that you have to "know what branch to go down before you start" in exactly the kind of way applicatives allow and monad preclude.
That's like saying "your program is more elegant if it has no monads". It's an incorrect statement. The monadic version is perfectly elegant. Even better: it's the right one.
In the non-continuous FRP literature[1], i.e. the kind you actually implement, SF a b = [a] -> [b], which is isomorphic to: Fold a -> Fold b, where Fold a = (exists s. (s, s -> (a, s))), which isomorphic to the type the author writes for transducer:
Yes, breadth first traversal of the solution space is very similar in spirit to our approach.
I have since completely rewritten the Haskell implementation. You should really check it out, especially if you are thinking about writing one of your own.
This implementation no longer requires a special coded repetition operator to get good complexity for regular and LL(k) grammars. This is a result of our progress w.r.t. performance of the theory since the paper's submission. My technique to achieve this uses structure derivatives (context based derivatives, or pseudo-equivalently, continuations) to avoid taking unnecessary parser derivatives. It in a sense "focuses" the parser computation on a small sub-parser.
Ping me if you have any questions; this paper has been getting passed around quite a bit lately and Matt and I have made progress on certain areas since the writing of the paper -- like that of the Rep hack.
I have since rewritten the Haskell implementation to compute fixed points on cyclic graphs without using pointers or Monads. Check it out if it interests you (git repo):
Here is the git repo (over http) for my Haskell implementation which exploits the technique to be linear for LL(k) (the Zip module is where this technique is implemented). The constant overhead for the implementation is still extremely high because we need to compute a fixed point computation on the whole parse graph for every input token. I'm working on getting all that down...
