Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Applicative WTF?

blog.plover.com

Post reply on HN
Print view View original

21–30 of 31 posts

Re: Applicative WTF?

#21

Post by lmm »

taejo wrote: post #17
nybble41 wrote: post #7

Earlier quoted context omitted.

Indeed, the learning process is important. I think it's particularly instructive to look at how `ap` is implemented, and what is left out in the transition from Monad to Applicative: mf `ap` ma = do f With a Monad, the action on the right of the bind operator is a function of the result of the action on the left. The second operand of the `ap` function, however, does not have any access to the result of the first ope…

Does this mean that many Monads have two possible Applicative instances? For the two orders of "running" mf and ma?

I don't know about "many", but certainly some - e.g. you could form a "reversed MonadWriter" applicative that would write the messages from ma before the messages from mf. For a lot of monads the effects are commutative though, in which case the "two possible" Applicatives are actually the same, e.g. Maybe obviously behaves the same whichever order you "run" mf and ma in.

Re: Applicative WTF?

#22

Post by pinjo »

nybble41 wrote: post #4
platz wrote: post #2

> Last time I used Haskell, Applicative wasn't even a thing. I had read the McBride and Paterson paper that introduced applicative functors, but that was years ago, and I didn't remember any of the details. In the previous post he learns how to use an Applicative. In this post, he learns how to define Applicative for a new type he's created. Yes, Applicative is abstract enough that it takes a few concrete examples to…

Given that he already knew how to define a Monad instance for his type, the Applicative instance could simply be: import Control.Monad (ap) instance Applicative Tree where pure = return ( ) = ap Also, given a Traversable instance—which is essentially just "fmap with effects"—one can get Foldable and Functor for free via foldMapDefault and fmapDefault. The really interesting cases are the ones where you can define an…

An example of this is the two possible applicative instance of list. One is based on the monad instance and does a cross product if presented with two lists. The other zips its arguments. It is the more interesting one imho:

    import Control.Applicative 
    newtype ZList a = ZList { runZList :: [a] } 
    instance Functor ZList where 
        fmap f = ZList . fmap f . runZList

    instance Applicative ZList where 
        pure a = ZList [a]
        () f x = ZList $ zipper (runZList f) (runZList x)
                where zipper (f:fs) (x:xs) = f x : zipper fs xs 
                      zipper [] _ = [] 
                      zipper _ [] = []
Difference of behaviour:

   *Main> ZipList [(*3),(*5),(*6)]  ZipList [1,2,3,4] 
    ZipList {getZipList = [3,10,18]}
   *Main> [(*3),(*5),(*6)]  [1,2,3,4]
    [3,6,9,12,5,10,15,20,6,12,18,24]
    *Main>

Re: Applicative WTF?

#23

Post by nybble41 »

pinjo wrote: post #22
nybble41 wrote: post #4

Earlier quoted context omitted.

Given that he already knew how to define a Monad instance for his type, the Applicative instance could simply be: import Control.Monad (ap) instance Applicative Tree where pure = return ( ) = ap Also, given a Traversable instance—which is essentially just "fmap with effects"—one can get Foldable and Functor for free via foldMapDefault and fmapDefault. The really interesting cases are the ones where you can define an…

An example of this is the two possible applicative instance of list. One is based on the monad instance and does a cross product if presented with two lists. The other zips its arguments. It is the more interesting one imho: import Control.Applicative newtype ZList a = ZList { runZList :: [a] } instance Functor ZList where fmap f = ZList . fmap f . runZList instance Applicative ZList where pure a = ZList [a] ( ) f x…

Yes, though that definition results in:

    pure id  ZipList [x, y, z] == ZipList [x]
and thus breaks one of the Applicative laws:

    pure id  v == v
The standard ZipList definition is `pure a = ZipList (repeat a)` (an infinite list).

The issue with defining a Monad instance for ZList is that mapping the function on the right of (>>=) over the ZList on the left gets you a ZList of `ZList b`, with no meaningful way to zip these ZLists together.

Re: Applicative WTF?

#24

Post by nybble41 »

taejo wrote: post #17
nybble41 wrote: post #7

Earlier quoted context omitted.

Indeed, the learning process is important. I think it's particularly instructive to look at how `ap` is implemented, and what is left out in the transition from Monad to Applicative: mf `ap` ma = do f With a Monad, the action on the right of the bind operator is a function of the result of the action on the left. The second operand of the `ap` function, however, does not have any access to the result of the first ope…

Does this mean that many Monads have two possible Applicative instances? For the two orders of "running" mf and ma?

All Applicatives have those two variants, not just Applicatives which are also Monads. There is a Backwards newtype in Control.Applicative.Backwards which reverses the order of effects for any Applicative:

    GHCi> import Control.Applicative.Backwards
    GHCi> :i Backwards
    newtype Backwards (f :: k -> *) (a :: k)
      = Backwards {forwards :: f a}
    GHCi> forwards $ (++)  Backwards ("foo"  Backwards ("bar"
As you can see, the result is the same but the effects are reversed. The definition is simple:

    instance Applicative f => Applicative (Backwards f) where
       pure = Backwards . pure
       Backwards f  Backwards a = Backwards $ (flip ($))  a  f

Re: Applicative WTF?

#25

Post by mikekchar »

lmm wrote: post #20
mikekchar wrote: post #13

It seems to me that people often overthink applicative. It falls right out of functor. Normally when you call fmap, you pass it a function that takes a single parameter. What happens if you pass it a function that takes more than one parameter (the other parameters being curried)? fmap applies a value from the functor to the function. Since it only passes one parameter, the result is a partially applied function. The…

> It seems to me that people often overthink applicative. It falls right out of functor. Normally when you call fmap, you pass it a function that takes a single parameter. What happens if you pass it a function that takes more than one parameter (the other parameters being curried)? fmap applies a value from the functor to the function. Since it only passes one parameter, the result is a partially applied function. T…

Cheers! That's a great example.

Re: Applicative WTF?

#26

Post by evincarofautumn »

lmm wrote: post #15
evincarofautumn wrote: post #12

Earlier quoted context omitted.

I think that law is slightly too restrictive; there’s a useful class of Monad instances where it doesn’t hold: commutative monads, in which: x Is equal to: y Provided that “x” is not free in “g”. A good example is an async monad that provides concurrency in ( ) and only blocks when there’s a data dependency in (>>=)—the result is the same regardless of evaluation order, but the implementations (and performance charac…

> the result is the same regardless of evaluation order, but the implementations (and performance characteristics) are different. You could handwave it away by arguing that they’re “morally equivalent”, but I think it pays to be precise about properties like commutativity of actions. You have to decide whether they're equivalent or they're not, and if they're not equivalent (for your purposes) you probably shouldn't…

I mean if you can’t observe any difference from safe code, then despite having different intensional/operational definitions, they are extensionally equivalent, and that’s mostly what I care about.

The ApplicativeDo desugaring, which uses the Applicative combinator instead of bind in exactly the circumstance I described above, was added specifically to support this use case when we (at Facebook) were writing Haxl, which is just such an example of a commutative monad; it’s built on IO, but doesn’t expose IO to safe code, so there’s no way to observe the concurrency from inside Haxl.

Granted, I’m biased because I have a somewhat unpopular definition of “effect” and “side effect”—if an effect can’t be observed from code by a particular observer that is safe wrt some property, then to me it’s not a side-effect.

It’s pretty widely accepted that within an ST action, mutating an STRef is a side effect to any observers within that action, but from the POV of the caller, the code is pure and thus side-effect–free; but I argue that mutating an IORef within an IO action is also not side-effectful, say from the POV of another thread, if the IORef is never shared—e.g.:

    -- Morally equivalent to “pure 1”.
    do
      x
Again, all I’m really saying is that you need to be precise about what model of effects you’re talking about, and what properties you guarantee re. safety, commutativity wrt other effects, &c.

Re: Applicative WTF?

#27

Post by lmm »

evincarofautumn wrote: post #26
lmm wrote: post #15

Earlier quoted context omitted.

> the result is the same regardless of evaluation order, but the implementations (and performance characteristics) are different. You could handwave it away by arguing that they’re “morally equivalent”, but I think it pays to be precise about properties like commutativity of actions. You have to decide whether they're equivalent or they're not, and if they're not equivalent (for your purposes) you probably shouldn't…

I mean if you can’t observe any difference from safe code, then despite having different intensional/operational definitions, they are extensionally equivalent, and that’s mostly what I care about. The ApplicativeDo desugaring, which uses the Applicative combinator instead of bind in exactly the circumstance I described above, was added specifically to support this use case when we (at Facebook) were writing Haxl, wh…

> if you can’t observe any difference from safe code, then despite having different intensional/operational definitions, they are extensionally equivalent, and that’s mostly what I care about.

That's true if the only things you care about are the things that are visible from safe code. But if you care about performance characteristics (which is presumably the whole point of this kind of monad) then code that gives the same result but has different performance characteristics is not equivalent for your purposes.

Ultimately, if x and y are marked as equivalent then a future maintainer will expect to be able to blindly replace x with y - and by convention that's true of and ap. So you shouldn't define and ap in such a way that replacing one with the other will change important characteristics of the code - you should only make things look equivalent in your code if they are equivalent for your purposes.

Re: Applicative WTF?

#28

Post by taejo »

lmm wrote: post #21
taejo wrote: post #17

Earlier quoted context omitted.

Does this mean that many Monads have two possible Applicative instances? For the two orders of "running" mf and ma?

I don't know about "many", but certainly some - e.g. you could form a "reversed MonadWriter" applicative that would write the messages from ma before the messages from mf. For a lot of monads the effects are commutative though, in which case the "two possible" Applicatives are actually the same, e.g. Maybe obviously behaves the same whichever order you "run" mf and ma in.

My "many" exactly meant to exclude the commutative case :)

Re: Applicative WTF?

#29

Post by nybble41 »

evincarofautumn wrote: post #26
lmm wrote: post #15

Earlier quoted context omitted.

> the result is the same regardless of evaluation order, but the implementations (and performance characteristics) are different. You could handwave it away by arguing that they’re “morally equivalent”, but I think it pays to be precise about properties like commutativity of actions. You have to decide whether they're equivalent or they're not, and if they're not equivalent (for your purposes) you probably shouldn't…

I mean if you can’t observe any difference from safe code, then despite having different intensional/operational definitions, they are extensionally equivalent, and that’s mostly what I care about. The ApplicativeDo desugaring, which uses the Applicative combinator instead of bind in exactly the circumstance I described above, was added specifically to support this use case when we (at Facebook) were writing Haxl, wh…

Was that last line supposed to be "readIORef x" instead of "pure x"? If you return the IORef then the result is equivalent to "newIORef 1", not "pure 1"—and newIORef does have observable side-effects. (Two IORefs are distinct even if they hold the same value.)

Re: Applicative WTF?

#30

Post by zzo38computer »

jmct wrote: post #8

The reason GHC won't infer the definition of Applicative is because there can be multiple valid `Applicative` instances for a type (unlike `Functor` where there is a unique (non-trivial) instance). The canonical example of this is lists, with 2 valid instances of `Applicative`. The author of the post seems to have this realization, but I wanted to call it out, just in case.

Any Applicative can be turned backward, although the backward way will not necessarily be compatible with the Monad instance, and also sometimes the backward one is same as the original way.
Post reply on HN