Haskell tutorial old text

A bit of category theory

Mathematicians love to abstract things. If a concept is generalizable they will try to find how to. And categories are a generalization of things like whole algebra systems, or whole logic systems...

And you know what can be seen as a category ? A type system too.

A category has two things:

• A collection of sets
• A collection of functions from one set (from the collection of sets) to another (also from the collection of sets)

It happens that Haskell just has that. If you think about types as sets (the type Int is the set of all integers, the type Bool is the set that contains the values True and False...), Haskell has a collection of types (so, a collection of sets). And Haskell happens to also have a collection of functions that work on these types show :: a -> String, odd :: Int -> Bool...

We call Haskell's category Hask.

Categories must follow somes rules but we won't cover them here. Just assume that Hask follows them. Don't try to understand it too much, it's juste the theorical base of Haskell, it is not really important when programming.

Functors

In category theory, a Functor, is a "function" from a category to another category. You can see functors like haskell functions of type SomeCategory -> SomeOtherCategory. If Hask is a category, we should have functors of type F :: Hask -> F(Hask) (Because we don't know the name of the output category, we just use F(Hask) as the name of F applied to Hask).

But earlier in this tutorial we saw something similar.

λ> :i []
type List :: * -> *
data List a = [] | a : [a]
        -- Defined in ‘ghc-prim-0.10.0:GHC.Types’
instance Monoid [a] -- Defined in ‘GHC.Base’
instance Semigroup [a] -- Defined in ‘GHC.Base’
instance Foldable [] -- Defined in ‘Data.Foldable’
instance Traversable [] -- Defined in ‘Data.Traversable’
instance Read a => Read [a] -- Defined in ‘GHC.Read’
instance Show a => Show [a] -- Defined in ‘GHC.Show’
instance Applicative [] -- Defined in ‘GHC.Base’
instance Functor [] -- Defined in ‘GHC.Base’
instance MonadFail [] -- Defined in ‘Control.Monad.Fail’
instance Monad [] -- Defined in ‘GHC.Base’
instance Eq a => Eq [a] -- Defined in ‘ghc-prim-0.10.0:GHC.Classes’
instance Ord a => Ord [a]
  -- Defined in ‘ghc-prim-0.10.0:GHC.Classes’

List is a function from types to types, it maps any type a to the type List a. But it needs one more thing. A way to transform functions on Hask types, to functions on List Hask types.

For two given types a, and b, we need to transform functions a -> b̀ to functions List a -> List b. Didn`t we see such function before ? Yes!

map :: (a -> b) -> ([a] -> [b])

So List seems to have everything needed to be a functor! In fact when looking at the List type, ghci told us that List IS a functor:

instance Functor [] -- Defined in ‘GHC.Base’

Lets look at the definition of the type class Functor`:

λ> :i Functor
type Functor :: (* -> *) -> Constraint
class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}
        -- Defined in ‘GHC.Base’
instance Functor ((,) a) -- Defined in ‘GHC.Base’
instance Functor ((,,) a b) -- Defined in ‘GHC.Base’
instance Functor ((,,,) a b c) -- Defined in ‘GHC.Base’
instance Functor ((,,,,) a b c d) -- Defined in ‘GHC.Base’
instance Functor ((,,,,,) a b c d e) -- Defined in ‘GHC.Base’
instance Functor ((,,,,,,) a b c d e f) -- Defined in ‘GHC.Base’
instance Functor ((->) r) -- Defined in ‘GHC.Base’
instance Functor IO -- Defined in ‘GHC.Base’
instance Functor [] -- Defined in ‘GHC.Base’
instance Functor Maybe -- Defined in ‘GHC.Base’
instance Functor Solo -- Defined in ‘GHC.Base’
instance Functor (Either a) -- Defined in ‘Data.Either’

The first line tells us something very interesting:

type Functor :: (* -> *) -> Constraint

Only types that have the kind * -> * can be Functors. So a simple Int cannot, and it's obvious since functors must be functions over types.

The second important thing we see is that all Functors must implement an object called fmap. Let's look at its type:

  fmap :: (a -> b) -> f a -> f b

It looks reaaaaaally similar to map:

  map  :: (a -> b) -> [a] -> [b]
  fmap :: (a -> b) -> f a -> f b

map has exactly the same type as fmap if you consider f to be the List type. So fmap for lists must be map. Let's try it:

λ> fmap length (words "hello world i am lily")
[5,5,1,2,4]
λ> map length (words "hello world i am lily")
[5,5,1,2,4]
λ> fmap odd [1,2,3,4]
[True,False,True,False]
λ> map odd [1,2,3,4]
[True,False,True,False]

They are indeed the same function!