4

I had a couple of hours of fun today trying to understand what the arrow operator applicative does in Haskell. I am now trying to verify whether my understanding is correct. In short, I found that for the arrow operator applicative

 (f <*> g <*> h <*> v) z = f z (g z) (h z) (v z)

Before I proceed, I am aware of this discussion but found it to be very convoluted and much more complicated than what I hope I derived today.

In order to understand what the applicative does I started from the definition of the arrow applicative in base

instance Applicative ((->) a) where
    pure = const
    (<*>) f g x = f x (g x)

and then proceeded to explore what the expressions

(f <*> g <*> h) z

and

(f <*> g <*> h <*> v) z

yield when expanded.

From the definition we get that

 f <*> g = \x -> f x (g x)

Because (<*>) is left associative, it follows that

 f <*> g <*> h = (f <*> g) <*> h
               = (\x -> f x (g x)) <*> h
               = \y -> (\x -> f x (g x)) y (h y)

Therefore

 (f <*> g <*> h) z = (\y -> (\x -> f x (g x)) y (h y)) z
                   = (\x -> f x (g x)) z (h z)
                   = (f z (g z)) (h z)
                   = f z (g z) (h z)

The last step is due to the fact that function application is left associative. Similarly

 (f <*> g <*> h <*> v) z = f z (g z) (h z) (v z)

This, to me, provides a very clear intuitive idea of what the arrow applicative does. But is this correct?

To test the result I ran, for example, the following,

λ> ((\z g h v -> [z, g, h, v]) <*> (1+) <*> (2+) <*> (3+)) 4
[4,5,6,7]

which conforms to the result derived above.

Before doing the expansion above I found this applicative very difficult to understand, since extremely complicated behaviour can result from its use because of currying. In particular, in

 (f <*> g <*> h <*> v) z = f z (g z) (h z) (v z)

functions can return other functions. Here is an example:

λ> ((\z g -> g) <*> pure (++) <*> pure "foo" <*> pure "bar") undefined
"foobar"

In this case z=undefined is ignored by all functions, because pure x z = x and the first function ignores z by construction. Furthermore, the first function takes only two arguments but returns a function taking two arguments.

  • 1
    Looks correct to me. – Mateusz Kowalczyk Oct 28 '17 at 17:24
  • 2
    Your intuition is exactly right. Next, you should tackle the `Monad` instance. In studying the instances for `(->) r`, you can also gain valuable intuitions for other applicatives and monads. – 4castle Oct 28 '17 at 17:31
  • Thanks guys! It's very mathematically rewarding to derive a result with pen and paper after noticing that an empirical approach to understanding fails miserably. And sure thing, monad instance next. –  Oct 28 '17 at 18:11
  • writing this with redundant parentheses might make it clearer and easier to read, like `(f <*> g <*> h <*> v) z = (f z) (g z) (h z) (v z)`. it is also `sequenceA [f,g,h,v] z = [f z, g z, h z, v z]`. in general, `instance Applicative ((->) x) where pure v x = v ; (f <*> g) x = (f x) $ (g x)` too can be easier to read. – Will Ness Oct 29 '17 at 09:31
  • Will, I like the symmetry in the form `(f z) (g z) (h z) (v z)`, but also like `f z (g z) (h z) (v z)` simply because it explicitly shows that there are four arguments supplied to `f.` –  Oct 29 '17 at 12:22
  • btw `(\z g -> g)` is just `pure id`. see? you thought about it in a special way, but it isn't special. It's an `id` supplied with *one* argument, `(++)`. :) I find it much [easier](https://stackoverflow.com/a/45516443/849891) to think with [combinatory](https://en.wikipedia.org/wiki/Combinatory_logic) equations, than with lambda definitions. `f = \x -> \y -> \z -> g` === `f x y z = g`, "what's the problem?" – Will Ness Oct 29 '17 at 20:25
  • your question is great as it shows that it is much easier to learn stuff when we put several/many related things side-by-side, like your `f<*>g<*>h` and `f<*>g<*>h<*>v`. Just one definition is usually given, for the `f<*>g`, which we need to "understand" then. But with multiple definitions, we can *see* the pattern. Human cognition is much tied up with our visual perception. This should be acknowledged and used more. Same with `sequenceA [f,g,h] z = [f z, g z, h z]`, which *looks* "the same" in a way, just "parens" are different. Multiple examples kind of "show" *why* a feature is needed. – Will Ness Oct 29 '17 at 20:32

1 Answers1

4

Yes, your calculations are correct.

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
  • I would add: `<*>` in the function applicative is the S combinator from combinatory logic: S *f* *g* *e* = *f* *e* (*g* *e*); it applies *f* to *g*, where each of them can access the “environment” *e*. – Jon Purdy Oct 29 '17 at 23:21