How to interpret fmap where f a = c -> d -> e

Question

I'm trying to understand some code and I'm getting myself tangled fairly well. Please help me to understand my logic, or lack thereof ...

To start:

*Main> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b

If I just want f a to be a function that takes one parameter, it's okay and makes sense:

*Main> :t \f -> fmap f (undefined :: String -> Int)
\f -> fmap f (undefined :: String -> Int) :: (Int -> b) -> String -> b

I can pass in a String in the second param, which generates an Int, and then use the function in the first param to generate the b.

Now, I want f a to be a function that takes two parameters, so I substitute that in:

*Main> :t \f -> fmap f (undefined :: String -> Int -> Bool)
\f -> fmap f (undefined :: String -> Int -> Bool) 
    :: ((Int -> Bool) -> b) -> String -> b

At this point, I'm confused. I already provided the function that converts from the String and the Int into the Bool. How can I now provide another function that takes a Int -> Bool to convert into a b? Is this non-sensical or am I not reading this right?

Or maybe this is a case of a functor within a functor and more needs to be done to make this make sense? In which case, what?

does it help you if you rephrase it as `fmap f (undefined :: String -> (Int -> Bool))`? Because this is what you are saying (basically `String` stays `String` but you replace `Int` with `Int -> Bool` to *match the needed pattern*) — Random Dev, Feb 14 '16 at 21:32
@Carsten I understand that grouping, but no it doesn't help me because I'm still left with the same type signature. If my function of type `String -> Int -> Bool` is opaque to me, then there'd be no way for me to implement this `fmap`. — , Feb 14 '16 at 21:55
no there is no way to implement the `fmap` fo `f a = (String -> Int) -> Bool -> a` - at least not directly - you can always wrap this into something like `newtype MyMap a = String -> Int -> Bool -> a` and make `MyMap` an instance of `Functor` - but then you have to wrap/unwarp the constructor — Random Dev, Feb 14 '16 at 22:02
Possible duplicate of [How to use (->) instances of Monad and confusion about (->)](http://stackoverflow.com/questions/5310203/how-to-use-instances-of-monad-and-confusion-about) — Cactus, Feb 15 '16 at 02:27

score 3 · Accepted Answer · edited Feb 15 '16 at 02:30

There is actually no such thing as a function with two parameters in Haskell. Every function has exactly one parameter.

In particular, String -> Int -> Bool is a function which accepts one String parameter. (Of course, knowing that the result is again a function you are able to use it as if it were a function with two parameters.) So if you want to unify this with f a, you need

f ~ (String->)
a ~ Int->Bool

Indeed Int->Bool can itself be interpreted as a functor-application^†

f ~ (String->)
g ~ (Int->)
b ~ Bool

so that String->Int->Bool ~ f (g b); thus

\f -> fmap (fmap f) (undefined :: String -> Int -> Bool)
       :: (Bool -> b) -> String -> Int -> b

I don't think the function family of functors is really a good example for grasping properties of functors/applicatives/monads. List and maybes are generally much less confusing; instead of the plain function functor the equivalent Reader is preferred when you need that functionality (pun not intended).

Regarding your original expression, that is actually not meaningless. If we translate it to a tamer functor, we could for instance write

> fmap ($2) [(>1), (>2), (>3)]
            [True, False, False]

Much the same thing can be done with the function functor:

> fmap ($2) (<) 1
True
> fmap ($2) (<) 2
False
> fmap ($2) (<) 3
False

Of course that example is a bit too simple to be useful, but you can also implement nontrivial ones.

^†_{Note that f and g are actually not the same functor. We tend to call them both “the function functor”, but really you get a different functor for every partial application of the (->) constructor. That means, you can't in any way unify the two layers, even though there's a Monad (a->) instance.}

You can unify the layers; you just can't do it with a standard `Monad`. You certainly can do something like `uncurry` generally. I would also guess that given an appropriate relationship between the argument types, you could probably do something with indexed monads. — dfeuer, Feb 15 '16 at 01:01
I think `\f -> fmap (fmap f) (undefined :: String -> Int -> Bool) :: (Bool -> b) -> String -> Int -> b` is what I was looking for. Thanks! — , Feb 15 '16 at 07:18

How to interpret fmap where f a = c -> d -> e

1 Answers1