8

I've been digging into Haskell for the past months, I've run into a situation with monads that I am not quite sure how to handle.

I have one value of type a -> m a and a second of type m (a -> a) and I need to compose them such that the result of the first ends up as the input into the of the second and produces a m (a -> a) if possible. I've been stuck on this for the past day now and I'm not wrapping my head around it. I suppose that I am looking for a function like (a -> m a) -> m (a -> a) -> m (a -> a). I can provide a more concrete example if it makes more sense.

Ben Doerr
  • 1,655
  • 1
  • 13
  • 23
  • 2
    You can *sort of* do what you ask if you're willing to perform the monadic actions associated with all possible input `a` values at once up front. Occasionally this is what you want -- but usually not. – Daniel Wagner Apr 05 '16 at 20:56
  • You need to add some laws to this type signature. Otherwise, an implementation could ignore the first argument and return the second without change. – winitzki Mar 11 '20 at 20:43

1 Answers1

13

You can't do this, in general. The problem is your result type: m (a -> a). This is a single monadic action which produces a function; but your first input has the form a -> m a, which (potentially) produces a different monadic action for each argument. So, for example, for the [] monad [a -> a] is list of functions with a fixed length, whereas a -> [a] can have a different length for each argument. So there's no way to 'push' the function type back into the m in general; see What is the general case of QuickCheck's promote function? for a related SO question.

If a -> m a would work for what you need, then you can turn your m (a -> a) argument into a -> m a using

\ x -> fmap ($ x) af

and use >=> (or <=<, it's not clear from your types) to compose the functions together.

Community
  • 1
  • 1
Jonathan Cast
  • 4,569
  • 19
  • 34
  • Yep! The asked-for function would downgrade a Monad action to an Applicative action, which is impossible. What they should do instead is upgrade the Applicative action to a Monad action. – Rein Henrichs Apr 05 '16 at 20:29
  • That's generally what I figured I was going to need to do. Just didn't have the words to reason about it yet. – Ben Doerr Apr 06 '16 at 13:16