[Haskell-cafe] ((a -> b) -> c) -> (a -> m b) -> m c

[Stuart Cook]

On 9/9/07, Henning Thielemann <lemming at henning-thielemann.de> wrote:
> If the signature would be
>    (Monad m) => ((a -> b) -> c) -> m (a -> b) -> m c
>     it would be possible, and the implementation would be 'liftM'/'fmap'.

Thanks, that's the kind of insight I was looking for.

Hmm. A key distinction between (a -> m b) and m (a -> b) is that in
the latter, the monadic component can't depend on the value given to
the function.

One of the particular cases I had in mind was an (a -> IO b) that
reads indexed values from a mutable data structure. It would be
possible to convert this to IO (a -> b) if you knew ahead of time what
reads you needed to do, without inspecting the "index" argument.

Of course, you'd be unable to use the index to restrict the amount of
reading necessary, which could be a problem for large structures. If
you end up reading most of the values anyway, it might still be worth
it.

> In the Reader monad you can even convert
>    (a -> m b)   to   m (a -> b)

Quite. In the ((->) r) monad, that's a conversion from (a -> r -> b)
to (r -> a -> b), which is just "flip".

I shall have to think about what properties are needed for a
conversion from (a -> m b) to m (a -> b), and what other structures
have those properties.

Actually, all this talk of m (a -> b) reminds me of applicative
functors, especially since you mentioned "fmap" (for vanilla functors)
above. More food for thought ...


Stuart