Why exactly would using applicative functors be inferior to monads for integer division?

user_609074 0
Viewed 163

I'm reading Graham Hutton's Programming in Haskell and am confused with the flow of thought outlined below.

He uses the example below to motivate the use of monads by showing the shortcomings of applicative functors for a divide operation where the return type is a Maybe to handle the error case indicating a potential division by zero scenario.

Given:

data Expr = Val Int | Div Expr Expr

safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv n m = Just (n `div` m)

eval :: Expr -> Maybe Int
eval (Val n) = pure n                               --type: Just(n)?
eval (Div x y) = pure safediv <*> eval x <*> eval y --type: Maybe(Maybe Int)?

He goes on to explain:

However, this definition is not type correct. In particular, the function safediv has type Int->Int->Maybe Int, whereas in the above context a function of type Int->Int->Int is required.

Replacing pure safediv by a custom defined function wound not help either, because this function would need to have type Maybe(Int->Int->Int), which does not provide any means to indicate failure when the second integer argument is zero. (X)

The conclusion is that the function eval does not fit the pattern of effectful programming that is captured by applicative functors. The applicative style restricts restricts us to applying pure functions to effectful arguments: eval does not fit this pattern because the function safediv that is used to process the resulting values is not a pure function, but may itself fail.

I'm not a Haskell programmer but from the type of eval (Div x y) it seems be that of Maybe(Maybe Int) - which can simply be squashed, no? (Something like a flatten in Scala or join in Haskell). What really is the issue here?

Irrespective of whether x,y are Just(s)/Nothing(s) it seems safediv will correctly evaluate - the only issue here is the return type which can be transformed appropriately. How exactly does the author go from his argument to this conclusion is what I'm having a hard time understanding.

...applicative style restricts restricts us to applying pure functions to effectful arguments

Also, why does paragraph marked (X) above make that claim when the problem just seems to be or return type misalignment.

I understand applicatives can be used for more efficiently chaining computations where the results of one don't impact the other - but in this case I'm rather confused as to how/where the failure would happen and if just a simple return type fix would solve the problem:

eval (Div x y) = join(pure safediv <*> eval x <*> eval y)

And does safediv have to be pure? AFAIK it could also be of type F[Maybe] or F[Either], no? What may I be missing? I can see where he's going but not sure if this is the right example to get there IMHO.

functional-programming haskell
1 Answers

I'm not a Haskell programmer but from the type of eval (Div x y) it seems be that of Maybe(Maybe Int) - which can simply be squashed, no? (Something like a flatten in Scala or join in Haskell). What really is the issue here? … the only issue here is the return type which can be transformed appropriately

This is the key issue! ‘Squashing’ is a fundamentally monadic operation — in fact, the type signature of join is join :: Monad m => m (m a) -> m a. If you restrict yourself to the applicative methods pure and (<*>), there is no way to implement this, but it becomes easy if you let yourself use (>>=) as well. Sure, you can easily implement flattenMaybe :: Maybe (Maybe a)) -> Maybe a without using monads, but that defeats the purpose of concepts like Applicative and Monad, which should be applicable to a wide range of types, not just Maybe.

Irrespective of whether x,y are Just(s)/Nothing(s) it seems safediv will correctly evaluate - the only issue here is the return type which can be transformed appropriately. How exactly does the author go from his argument to this conclusion is what I'm having a hard time understanding.

...applicative style restricts restricts us to applying pure functions to effectful arguments

Also, why does paragraph marked (X) above make that claim when the problem just seems to be or return type misalignment.

The idea here is this. Let’s say you have two functions, and two values:

nonEffectful :: a -> b -> c
effectful    :: a -> b -> m c

effectfulA :: m a
effectfulB :: m b

Now, if you want to apply the nonEffectful function to the two effectful arguments, m only needs to be Applicative: it’s easy to do nonEffectful <$> effectfulA <*> effectfulB :: m c. But if you try that with the effectful function instead, you run into a problem: you get a return type of m (m c) instead of m c. To ‘squash’ m (m c) into m c, you need a Monad instance. So applicatives can only apply pure (non-effectful) functions to effectful arguments, but monads let us apply effectful functions to effectful arguments. This is what Hutton was attempting to do this, but with a specific function safeDiv :: Int -> Int -> Maybe Int.

(One thing I didn’t mention in the above discussion is intuition: why, on an intuitive rather than formal level, are monads required for specific computations? As you have already noticed, the answer has to do with dependency. For nonEffectful <$> effectfulA <*> effectfulB, the two effectful values have no impact on each other. However, with effectful <$> effectfulA <*> effectfulB, suddenly there is a dependency: the effectful function must depend on the results of the effectful computations passed to it. Monad can be thought of as representing the idea of effectful computations which can depend on each other, whereas Applicative represents the idea of effectful computations which cannot depend on each other (although a pure function may depend on them). Similarly, in order to evaluate a nested computation m (m a), you first need to evaluate the outer computation, and then evaluate the resulting inner effectful computation. Again we have an effectful computation which depends on another effectful computation, so this requires a Monad.)

user_73452980
Related