Functors and Applicatives

Functors and Applicative Functors are key typeclasses in Haskell that provide foundational abstractions for working with values in contexts. For related abstractions, see Monads Basics, Common Monads, and Polymorphism.

Functors

A functor represents a type that can be mapped over. Intuitively, it’s a container or context that allows us to apply functions to the values inside without affecting the structure. For examples of functor instances, see Lists and List Comprehensions, Algebraic Data Types, and Introduction to IO.

The Functor Typeclass

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

fmap applies a function to the value(s) inside the functor, preserving the structure.

There’s also an infix operator for fmap:

(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap

Functor Laws

For a type to be a valid functor, it must satisfy two laws. These laws are analogous to the monad laws (see Monad Laws) and ensure predictable behavior.

1. Identity Law: fmap id = id
   • Mapping the identity function should not change anything
2. Composition Law: fmap (f . g) = fmap f . fmap g
   • Mapping a composition of functions should be the same as mapping one function after the other

Common Functors

List Functor

instance Functor [] where
  fmap = map

Example:

fmap (*2) [1, 2, 3]  -- [2, 4, 6]
(*2) <$> [1, 2, 3]   -- [2, 4, 6]

Maybe Functor

instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just a) = Just (f a)

Example:

fmap (*2) (Just 3)   -- Just 6
fmap (*2) Nothing    -- Nothing

Either Functor

instance Functor (Either a) where
  fmap _ (Left e) = Left e
  fmap f (Right x) = Right (f x)

Example:

fmap (*2) (Right 3)   -- Right 6
fmap (*2) (Left "error")  -- Left "error"

IO Functor

instance Functor IO where
  fmap f action = do
    result <- action
    return (f result)

Example:

fmap length getLine   -- IO Int - reads a line and returns its length

Creating Custom Functors

Any type with a single type parameter can potentially be a functor. For more on custom data types, see Algebraic Data Types.

data Tree a = Leaf | Node a (Tree a) (Tree a)
 
instance Functor Tree where
  fmap _ Leaf = Leaf
  fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)

Practical Uses of Functors

1. Transforming wrapped values:

   fmap show (Just 42)  -- Just "42"

2. Working with computations:

   userInput <- fmap read getLine  -- Read user input as a number

3. Applying functions to containers:

   fmap (filter even) [[1,2,3], [4,5,6]]  -- [[2], [4,6]]

Applicative Functors

Applicative functors extend the concept of functors by allowing functions wrapped in a context to be applied to values in the same context. Applicative is a superclass of Monad (see Monads Basics).

The Applicative Typeclass

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

• pure wraps a value in the minimal context
• <*> (pronounced “apply”) applies a function in a context to a value in a context

Applicative Laws

Valid applicative instances must satisfy several laws, which are similar in spirit to the monad laws (Monad Laws).

1. Identity: pure id <*> v = v
2. Homomorphism: pure f <*> pure x = pure (f x)
3. Interchange: u <*> pure y = pure ($ y) <*> u
4. Composition: pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

Common Applicatives

Maybe Applicative

instance Applicative Maybe where
  pure = Just
  Nothing <*> _ = Nothing
  (Just f) <*> something = fmap f something

Example:

(+1) <$> Just 3
pure +) <*> Just 3        -- Just 4
Just (+1) <*> Just 3        -- Just 4
Just (+) <*> Just 3 <*> Just 5  -- Just 8
Nothing <*> Just 3          -- Nothing

List Applicative

instance Applicative [] where
  pure x = [x]
  fs <*> xs = [f x | f <- fs, x <- xs]

Example:

[(*2), (+3)] <*> [1, 2, 3]  -- [2, 4, 6, 4, 5, 6]

The list applicative produces all possible combinations of applying each function to each value.

IO Applicative

instance Applicative IO where
  pure = return
  aF <*> aX = do
    f <- aF
    x <- aX
    return (f x)

Example:

pure (+) <*> getLine <*> getLine  -- Reads two lines and adds them as numbers

Helper Functions for Applicatives

-- Apply a function to two applicative values
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 f a b = f <$> a <*> b
 
-- Sequential application
(*>) :: Applicative f => f a -> f b -> f b
a *> b = (id <$ a) <*> b
 
-- Sequence actions, discard value from the right
(<*) :: Applicative f => f a -> f b -> f a
a <* b = liftA2 const a b

Practical Uses of Applicatives

Applicative functors are used extensively in parser combinators (Parser Combinators), property-based testing (Property-Based Testing), and in composing effects in functional programs (Monads Basics, Common Monads).

1. Combining independent computations:

   data Person = Person { name :: String, age :: Int }
    
   validatePerson :: String -> Int -> Maybe Person
   validatePerson name age =
     Person <$> validateName name <*> validateAge age

2. Working with multiple Maybe values:

   lookupUser :: UserId -> Maybe User
   lookupSetting :: SettingId -> Maybe Setting
    
   combinedLookup :: UserId -> SettingId -> Maybe (User, Setting)
   combinedLookup uid sid = (,) <$> lookupUser uid <*> lookupSetting sid

3. Parallel validation:

   data Validation e a = Failure e | Success a
    
   instance Semigroup e => Applicative (Validation e) where
     pure = Success
     Failure e1 <*> Failure e2 = Failure (e1 <> e2)
     Failure e <*> _ = Failure e
     _ <*> Failure e = Failure e
     Success f <*> Success a = Success (f a)

4. Parsing with Applicatives:

   -- Using a parser combinator library
   parseFullName :: Parser FullName
   parseFullName = FullName <$> parseFirstName <*> parseLastName

The Relationship Between Functors, Applicatives, and Monads

These typeclasses form a hierarchy with increasing power:

1. Functor: Ability to map functions over a context

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

2. Applicative: Ability to apply wrapped functions to wrapped values

   (<*>) :: f (a -> b) -> f a -> f b

3. Monad: Ability to sequence computations that depend on previous results

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

The relationship can be summarized as:

• Every Monad is an Applicative
• Every Applicative is a Functor
• Functors are the most general, Monads are the most specific

The key differences are in how they handle contexts and dependencies:

• Functors apply functions to values in a context
• Applicatives apply functions in a context to values in a context
• Monads use the result of one computation to determine the next computation

When to Use Each

• Use Functor when you just need to transform values inside a context
• Use Applicative when you need to combine independent values in contexts
• Use Monad when each step depends on the result of the previous step

Key Points to Remember

1. Functors let you apply a function to a value in a context, preserving the structure
2. The key functor operation is fmap or <$>
3. Applicative functors let you apply a function in a context to a value in a context
4. The key applicative operations are pure and <*>
5. Applicatives are more powerful than functors but less powerful than monads
6. Applicatives excel at combining independent computations

Haskell:

\x -> \y -> x + y
-- Or equivalently
\x y -> x + y

Many Haskell concepts can be traced back to lambda calculus:

• Anonymous functions (lambdas) (Functions and Equations)
• Higher-order functions (Higher-Order Functions)
• Currying (Functions and Equations)
• Lazy evaluation (similar to normal-order evaluation in lambda calculus; see Evaluation Strategies)

Evaluation Strategies

Normal Order Evaluation

In normal order evaluation (which Haskell uses a variant of), function arguments are substituted without being evaluated, and then the resulting expression is evaluated. For more, see Evaluation Strategies.

Church-Rosser Theorem

The Church-Rosser theorem states that if an expression can be reduced in two different ways, then there exists a common form that both reduction paths eventually reach. This property is also discussed in Expressions and Reduction.

Computability and the Lambda Calculus

The lambda calculus is Turing complete, meaning it can express any computable function. This was one of the key insights that led to the development of modern computers.

Examples in Haskell

…