Over the next several weeks, we will study several type classes which play a central role in Haskell programming; they describe really common and powerful patterns of computation.
To work up to this, let's do a bit of programming. Recall the definition of the Maybe type, which can be used in many cases to encode either "failure" or a "successful" result. We will see examples of:
Maybe values,Maybe functions to Maybe arguments, andMaybe "actions."Maybe ValuesLet's write a couple routine recursive definitions that "map over" Maybe values.
addOne :: Num a => Maybe a -> Maybe a
addOne Nothing = Nothing
addOne (Just n) = Just $ 1 + n
square :: Num a => Maybe a -> Maybe a
square Nothing = Nothing
square (Just n) = Just $ n * n
maybeLength :: Maybe [a] -> Maybe Int
maybeLength Nothing = Nothing
maybeLength (Just xs) = Just $ length xs
maybeShow :: Show a => Maybe a -> Maybe String
maybeShow Nothing = Nothing
maybeShow (Just x) = Just $ show xAs usual when seeing repeated structure in our code, we look for ways to streamline, in this case by factoring out the mapping function.
mapMaybe :: (a -> b) -> Maybe a -> Maybe b
mapMaybe f Nothing = Nothing
mapMaybe f (Just x) = Just $ f x
addOne = mapMaybe (1+)
square = mapMaybe (^2)
maybeShow = mapMaybe showThe type and expression structure of mapMaybe should look familiar. Recall our old friend map that "maps over" lists.
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xsVery many types arise in programming where having this kind of general map function is useful. So, treating them uniformly in the language will reap benefits. Stay tuned.
Maybe FunctionsmapMaybe works well for functions with one argument...
mapMaybe (+2) (Just 10) -- Num a => Maybe a... but doesn't help with more:
mapMaybe (+) (Just 10) -- Num a => Maybe (a -> a)
mapMaybe (+) (Just 10) (Just 2) -- type errorWe also want to be able to apply Maybe functions.
pureMaybe :: a -> Maybe a
pureMaybe = Just
applyMaybe :: Maybe (a -> b) -> Maybe a -> Maybe b
applyMaybe (Just g) (Just x) = Just $ g x
applyMaybe _ _ = NothingNow we can handle multi-arg Maybe functions:
> pureMaybe (+) `applyMaybe` Just 10 -- Num a => Maybe (a -> a)
> pureMaybe (+) `applyMaybe` Just 10 `applyMaybe` Just 2 -- Num a => Maybe a
> pureMaybe (+) `applyMaybe` Nothing `applyMaybe` Just 2
> Nothing `applyMaybe` Nothing `applyMaybe` Just 2We can write helper functions to "lift" pure functions with different arities. For example:
lift3Maybe :: (a -> b -> c -> d) -> Maybe a -> Maybe b -> Maybe c -> Maybe d
lift3Maybe f ma mb mc =
pureMaybe f `applyMaybe` ma `applyMaybe` mb `applyMaybe` mcNotice that, because
mapMaybe :: {- forall t1, t2. -} (t1 -> t2) -> Maybe t1 -> Maybe t2
mapMaybe f :: Maybe a -> Maybe (b -> c -> d)we can call mapMaybe f in place of applyMaybe (pureMaybe f).
lift3Maybe f ma mb mc =
f `mapMaybe` ma `applyMaybe` mb `applyMaybe` mcIt is a common pattern to apply a function of arity n to n Maybe arguments. This will arise for very many other types, too. Stay tuned.
Maybe ActionsMotivating example:
type Person = String
father :: Person -> Maybe Person
father = undefined -- assuming this is defined in some reasonable way
grandfather :: Person -> Maybe Person
grandfather p =
case father p of
Nothing -> Nothing
Just fp ->
case father p of
Nothing -> Nothing
Just ffp -> Just ffpCan avoid the second case expression...
grandfather :: Person -> Maybe Person
grandfather p =
case father p of
Nothing -> Nothing
Just fp -> father pbut still, it is tedious to manipulate Nothing and Just values explicitly. However, neither mapMaybe nor applyMaybe can help here; the second function call, father p, returns Nothing or Just some value depending on the value of p.
We might start by defining something like applyMaybe but where the (Maybe) function returns a Maybe value:
foo :: Maybe (a -> Maybe b) -> Maybe a -> Maybe b
foo (Just f) (Just a) = f a
foo _ _ = NothingThis is fine, but is actually doing more work (and is more restrictive) than needed; it's redoing part of what applyMaybe does.
Instead:
applyMaybeFancy :: (a -> Maybe b) -> Maybe a -> Maybe b
applyMaybeFancy _ Nothing = Nothing
applyMaybeFancy f (Just x) = f x(EXERCISE: Define foo in terms of applyMaybe and applyMaybeFancy.)
Now we can avoid manipulating Nothing explicitly:
grandfather p =
father `applyMaybeFancy` (father `applyMaybeFancy` (Just p))If we flip the arguments to applyMaybeFancy
andThenMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b
andThenMaybe = flip applyMaybeFancythen it looks more like sequencing the function calls one after another from left-to-right:
grandfather p =
father p `andThenMaybe` (\fp ->
father fp `andThenMaybe` (\ffp ->
Just ffp
))Or:
grandfather p =
father p `andThenMaybe` \fp ->
father fp `andThenMaybe` \ffp ->
Just ffpsibling :: Person -> Person -> Bool
sibling x y =
case (father x, father y) of
(Just fx, Just fy) -> fx == fy && x /= y
_ -> FalseThere are a couple aspects that are undesirable. The first is that we should perform the x /= y comparison before forcing either father x or father y to evaluate.
sibling x y =
x /= y && sameParent where
sameParent =
case (father x, father y) of
(Just fx, Just fy) -> fx == fy && x /= y
_ -> FalseThe other is that we have to manually pattern match to get to the interesting, non-error case. If we encode Bools using Maybe
guardMaybe :: Bool -> Maybe ()
guardMaybe True = Just ()
guardMaybe False = Nothingthen we can reuse the Maybe sequencing:
sibling :: Person -> Person -> Maybe ()
sibling x y =
(guardMaybe $ x /= y) `andThenMaybe` \() ->
father x `andThenMaybe` \fx ->
father y `andThenMaybe` \fy ->
guardMaybe $ fx == fyNotice that we changed the type of sibling, but it's trivial to convert from Maybe () back to Bool.
Lot's of other types of values will have notions of sequencing actions. Stay tuned.
It is a common pattern to apply a function of arity n to n Maybe arguments. To make this common case look as close to function application as possible, we can define two helper infix operators.
(<$>) = mapMaybe
(<*>) = applyMaybeNow, the arity-n pattern above can be written in applicative style:
lift2Maybe f ma mb =
f <$> ma <*> mb
lift3Maybe f ma mb mc =
f <$> ma <*> mb <*> mc
lift4Maybe f ma mb mc md =
f <$> ma <*> mb <*> mc <*> mdFor example:
> mapMaybe (+) (Just 1) (Just 2)
> (+) <$> Just 1 <*> Just 2By defining an infix operator for andThenMaybe
(>>=) = andThenMaybewe can write sequences of Maybe actions as:
grandfather p =
father p >>= \fp ->
father fp >>= \ffp ->
Just ffp
sibling x y =
(guardMaybe $ x /= y) >>= \() ->
father x >>= \fx ->
father y >>= \fy ->
guardMaybe $ fx == fyRecall the last version of grandfather above. We can eta-reduce the innermost lambda:
grandfather p =
father p `andThenMaybe` (\fp -> father fp `andThenMaybe` Just)And, based on the definition of andThenMaybe:
grandfather p =
father p `andThenMaybe` fatherThis pattern of function composition can be abstracted:
(<=<) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c)
(f <=< g) x = g x `andThenMaybe` fAnd now:
grandfather = father <=< fatherWe've seen a bunch of useful functions for manipulating Maybe values.
pureMaybe :: a -> Maybe a
mapMaybe :: (a -> b) -> (Maybe a -> Maybe b)
applyMaybe :: Maybe (a -> b) -> (Maybe a -> Maybe b)
flip andThenMaybe :: (a -> Maybe b) -> (Maybe a -> Maybe b)
andThenMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b
guardMaybe :: Bool -> Maybe ()For each of the above, we can replace Maybe with many other different types t and implement suitable definitions with analogous type signatures and behavior:
pure :: Applicative_ => a -> t a
map :: Functor_ => (a -> b) -> (t a -> t b)
apply :: Applicative_ => t (a -> b) -> (t a -> t b)
flip andThen :: Monad_ => (a -> t b) -> (t a -> t b)
andThen :: Monad_ => t a -> (a -> t b) -> t b
guard :: MonadPlus_ => Bool -> t ()The constraints above preview type classes that will house each pattern of computation. In the next several sections, we'll study these — and other — common patterns of computation. You may find it useful to refer back to this "Monad Roadmap" from time to time.