Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What means precisely "function inside a functor"

In category theory functor is a homomorphism between two categories. In Haskell, it's said that applicative functor allows us to apply functions "inside a functor". Could one translate that words "function inside a functor" back to mathematics or give some other insight? (I know that functor can be Maybe, [] etc. but still struggle to comprehend that notion.)

like image 701
Cartesius00 Avatar asked Dec 06 '12 22:12

Cartesius00


People also ask

Is a functor a function?

Functors are objects that behave as functions. They are class objects which can overload the function operator() and act as function themselves. They can encapsulate their own function which is executed when needed.

What is a pointed functor?

A pointed functor is really a functor F together with a function of defined for every type a , and sending a value x of type a into a value of(x) of type F a .

What is a functor in programming?

In functional programming, a functor is a design pattern inspired by the definition from category theory, that allows for a generic type to apply a function inside without changing the structure of the generic type. This idea is encoded in Haskell using type class.

What are functor laws?

Functor Laws If two sequential mapping operations are performed one after the other using two functions, the result should be the same as a single mapping operation with one function that is equivalent to applying the first function to the result of the second.


2 Answers

My category theory is not strong at all (I started from the programming side of Haskell and have been recently trying to learn some of the category theory foundations of some of its concepts). But here's what I've got:

In Haskell, a functor is a type constructor, meaning it maps from general types to "types in the functor".

In category theory, a functor maps from the objects of one category to the objects of another category.

When applying category theory to Haskell, we imagine that we're working with the category Hask, the category of Haskell types.

So Haskell functors aren't general category theory functors; they all map from Hask to a sub-category of Hask (because the type f a for some functor f and arbitrary type a is still a Haskell type). For example the Maybe functor maps objects (types) in Hask to the category of types of the form Maybe a.

Functions are first-class in Haskell, so function types are perfectly ordinary types (and are objects of Hask) so functors also map function types to "function types in the functor". So the phrase "a function inside a functor" is a shorthand for a value in a type that results from applying a functor to a function type. e.g. Just (+1) is one particular value in the type Maybe (Int -> Int), which is the object (type) to which the Maybe functor maps the object Int -> Int.

So an "applicative functor" is a functor which has some extra rules, which are sufficient to take values which are functions in types which are objects of the functor's "destination" category, and apply those values to other values in types in the destination category.

Using Maybe again as an example, if we only knew it was a functor that gives us a correspondence between the objects Int -> Char and Maybe (Int -> Char), and between the objects Int and Maybe Int, and between the objects Char and Maybe Char. But while we have the ability to take a value in Int -> Char and a value in Int and produce a value in Char, Maybe being a functor doesn't guarantee that we have any ability to do some corresponding operation with a value in Maybe (Int -> Char) and a value in Maybe Int.

When we also know it's an applicative functor, then we do have an ability to take a value in Maybe (Int -> Char) and a value in Maybe Int and produce a value in Maybe Char, and this satisfies certain properties wrt the application of Int -> Char values to Int values.

As far as I know, applicative functors aren't terribly interesting from a pure category theory standpoint. Perhaps this is because category theory is concerned with relationships between objects, which correspond to types in Haskell, but from a programming perspective applicative functors are motivated by relationships between values in those types? (we want the values in the "function types" obtained by using the functor to still be able to be applied to things to do computation).

like image 160
Ben Avatar answered Sep 21 '22 07:09

Ben


Translation Back to Math

In a closed monoidal category there is a notion of "exponent" which "internalizes" the morphism relation. You can then evaluate these exponents. That is, you have a way of saying (excuse my notion, Stackoverflow lacks mathjax)

eval : (a ~> b,a) -> b

as well as meta operations for currying and uncurrying.
An "applicative functor" maps exponents in an "applicable" way, F (a ~> b) can be combined with an F a to get an F b. This is because applicative functors are monoidal functors, so they have an operation (in the target category)

f a -> f b -> f (a,b)

which when you also fmap eval gives you ap from Haskell.

I doubt that was usefull,

The Haskell

The best way to understand an applicative functor is to look at the type

class Functor f => Applicative f where
  pure :: a -> f a
  <*>  :: f (a -> b) -> f a -> f b

the trivial example is

newtype Id a = Id a
instance Applicative Id where
  pure a = Id a
  Id f <*> Id a = Id (f $ a)

Id is also a Monad. In fact, all Monads are Applicative.

pure = return
mf <*> mx = do f <- mf
               x <- mx
               return (f x)

a more interesting example though is infinite sequences

data Seq a = Seq a (Seq a)
instance Applicative Seq where
  pure a = Seq a (pure a)
  (Seq f fs) <*> (Seq x xs) = Seq (f x) (fs <$> xs)

You can think of this as being equivalent to zipWith $ on lists. All Monads are Applicative, but I think the infinite sequence is fun because the corresponding monad instance is...non obvious (and rather slow). It will be left as an exercise to the reader (btw, I am steeling this example/exercise from something I remember reading that I think pigworker wrote on this site).

like image 24
Philip JF Avatar answered Sep 20 '22 07:09

Philip JF