16

In Haskell, what does ((->) t) mean in the type signature of instances? For example Functor, Applicative and Monad all have an instance along the lines of:

Functor ((->) r)

I can't find any explanation of what this type signature means and it's highly search engine-resistant.

APerson
  • 8,140
  • 8
  • 35
  • 49
drt
  • 888
  • 1
  • 8
  • 19
  • 3
    `highly search engine-resistant` -- not for the SO search engine. See http://stackoverflow.com/q/5310203/11683 – GSerg Sep 01 '13 at 19:12
  • 1
    You're right! I guess I should consider sometimes searching SO directly instead of just relying on Google. – drt Sep 01 '13 at 19:40
  • You can also search on [SymbolHound](http://www.symbolhound.com/?q=Functor+%28%28-%3E%29+r%29). – Joan Charmant Sep 03 '13 at 18:48
  • 1
    In case anyone who happens across this question is wondering, a good search term is "reader monad". – dfeuer Jan 02 '15 at 05:21

3 Answers3

19

-> is an infix type constructor. You can compare it with : - an infix value constructor for list type. To use : alone we put parentheses around it so it becomes a prefix function application:

(:) a b is the same as a : b

Similarly, (->) a b is the same as a -> b, type of a function from a to b.

(->) a is a partial application of type constructor, and itself a type constructor of kind * -> *.

You can think of it as "a constructor of types of functions from a". E.g. (->) Int is a constructor of types of functions from Int. You can construct full function type by passing another type to it: (->) Int String is the type of functions from Int to String.

instance Functor (->) a is a functor with fmap operation transforming an a -> b function into an a -> c function. You can compare it with a similar instance Functor (Either a) which maps Either a b to Either a c by applying the fmap argument to Right values.

Lambda Fairy
  • 13,814
  • 7
  • 42
  • 68
nponeccop
  • 13,527
  • 1
  • 44
  • 106
  • Thanks. This mostly makes sense to me. Still somewhat new to Haskell so it will take me some time to digest. – drt Sep 01 '13 at 19:42
  • 8
    The `(->) r` instances are *very* difficult to understand, in my opinion. I feel relatively confident with a lot of Haskell, but I still have no intuition at all for how the `(->) r` instances work. I can *use* them, because I use them all the time, so it isn't very weird to me anymore. It's just that I wouldn't say I understand them deeply. Don't worry if you don't either. I'm sure it will come to both of us in time. – kqr Sep 01 '13 at 20:19
  • @kqr When you know what the Monad instance does, I think you can derive it in a nice way. This small note I've written starts with a very verbose (but I hope somewhat easy to understand) definition of `>>=`, and then shows how, when properly golfed, it is identical to the usual implementation you may know from LYAH for example. https://github.com/quchen/articles/blob/master/reader_instance_derived.md#bind – David Sep 12 '13 at 13:50
  • @kqr Yeah, `(->) r` is really weird. Like, it allows you to re-write `diag f x = (x, x)` in point-free style as... `diag = join (,)`! When the lambdabot told me that, my reaction was "wat." – Joker_vD Sep 14 '13 at 15:35
12

We could use lambda functions and infix functions:

(->) a    =    \b ->  (->) a b  --pseudo-Haskell
(->) a    =    \b ->  a -> b    --pseudo-Haskell

so, read instance as:

class Functor f where
   fmap :: (a->b) -> f a -> f b

instance Functor ((->)r) where
   fmap :: (a->b) -> f     a  -> f     b
         = (a->b) -> (->)r a  -> (->)r b   --pseudo-Haskell
         = (a->b) -> (r -> a) -> (r -> b)  --pseudo-Haskell
wit
  • 1,612
  • 10
  • 10
  • 1
    This was actually quite helpful for my intuition. I need to do the same thing for the applicative instance of `(->) r`! – kqr Sep 01 '13 at 20:21
4

You could see it as the set of types r -> a where r is fixed.

A functor is a type function m, which means that for any type a you have a type m a. Examples are Maybe, [] and (->) r. The latter should perhaps better be written (r ->), but I don't know if that's allowed.

md2perpe
  • 3,372
  • 2
  • 18
  • 22