ARTICLE

Abstracting Computations with Type Classes

From Haskell in Depth by Vitaly Bragilevsky

Figure 1. Type classes for abstracting computations
  • Operation — For abstracting binary operations (combining two values into one of the same type)
  • Computational context — For computing the value of some type in a context, and that computation can be accompanied by some effects
  • Iteration — For repeated computations over some structure, potentially collecting the results in a context

The only operation, (<>)

When using these two type classes, Semigroup and Monoid, keep one simple rule in mind— provide a generic binary operation over the values of any datatype that defines their instances. The type class Semigroup declares such an operation as:

(<>) :: Semigroup a => a -> a -> a
ghci> import Data.Semigroup ghci> [1,2,3] <> [4,5,6] [1,2,3,4,5,6] ghci> "Hello " <> "world" "Hello world" ghci> Sum 2 <> Sum 3 Sum {getSum = 5} ghci> Product 2 <> Product 3 Product {getProduct = 6}
mempty :: Monoid a => a
ghci> mempty :: [Int] [] ghci> mempty :: String ""
ghci> mempty :: Sum Int Sum {getSum = 0}
ghci> mempty :: Product Int
Product {getProduct = 1}
mempty <> a == a a <> mempty == a
ghci> import Data.Text ghci> :info Text data Text instance Monoid Text -- Defined in 'Data.Text' instance Semigroup Text -- Defined in 'Data.Text'
ghci> :set -XOverloadedStrings ghci> h = "hello" :: Text ghci> c = ", " :: Text ghci> w = ", world" :: Text ghci> h <> c <> w "hello, world"
sconcat :: Semigroup a => Data.List.NonEmpty.NonEmpty a -> a mconcat :: Monoid a => [a] -> a
ghci> 0 :| [1,2,3] 0 :| [1,2,3] ghci> "x" :| [] "x" :| []
ghci> sconcat ("x" :| ["y", "z"]) "xyz"

Mapping, applying, and sequencing in a computational context

Let’s pick apart the title of this subsection. Merriam–Webster gives the following definition of context: the interrelated conditions in which something exists or occurs

  • Functor abstracts mapping over some value in a computational context.
  • Applicative enables applying a function in a context to a value in a context and injecting value into a context.
  • Monad allows sequencing of computations in a context to structure what’s done in the next computation depends on the result of the previous one.
fmap :: Functor f => (a -> b) -> f a -> f b pure :: Applicative f => a -> f a (<*>) :: Applicative f => f (a -> b) -> f a -> f b
(>>=) :: Monad m => m a -> (a -> m b) -> m b

Exploring different contexts in parallel

The type classes we’re talking about share common ideas about behavior. It’s always instructive to go both ways, from common ideas to specific implementations and vice versa. In this subsection you’re advised to follow the path of understanding from particular examples toward general notions. We’ll focus on these three contexts:

  • IO, which allows you to do input/output
  • Writer, which supports logging of additional information along with the process of computations (you can get access to this context after importing the module Control.Monad.Writer)
  • [] (a list), which is the most unusual context of nondeterministic computations
  • getLine :: IO String is a value of type String in a context which is responsible for acquiring it from a side effect of reading user input.
  • writer (42, "step 1\n") :: Writer String Int is a value 42 of type Int which is accompanied by the log "step 1\n" in the form of a String.
  • [1,2,3] :: [Int] is one of the values 1, 2, or 3 of type Int, but we aren’t sure which one is the result of the computations (this uncertainty is what I call nondeterminism).
ghci> fmap (++"!") getLine Hi
"Hi!"
ghci> fmap (+1) (writer (42, "step 1\n")) :: Writer String Int WriterT (Identity (43,"step 1\n"))
ghci> fmap (+1) [1,2,3] [2,3,4]
ghci> pure (++) <*> getLine <*> getLine hello world "helloworld"
ghci> pure (+) <*> writer (42, "step 1\n") <*> writer (10, "step 2\n") :: Writer String Int WriterT (Identity (52,"step 1\nstep 2\n")) ghci> pure (+) <*> [1,2,3] <*> [4,5,6]
[5,6,7,6,7,8,7,8,9]
ghci> getLine >>= putStrLn hello hello
ghci> writer (42, "step 1\n") >>= (\a -> writer (a+1, "step 2\n")) :: Writer String Int WriterT (Identity (43,"step 1\nstep 2\n")) ghci> [1,2] >>= (\x -> [x-1, x, x+1])
[0,1,2,1,2,3]

do notation

do notation is a convenient syntactic mechanism for expressing monadic computations, which includes:

  • Sequencing of operations by writing them one after another (as in imperative programming languages)
  • Binding values in a context to names with
  • Constructing succeeding operations with the names bound previously (this is the main feature of the Monad type class)
action t = do   a <- f t
b <- g a
h a
return (k a b)
action t =   f t >>= \a ->
a >>= \b ->
a >>
return (k a b)
action t = f t >>= \a -> g a >>= \b -> h a >> return (k a b)
readNumber :: IO Int readNumber = do   s <- getLine
return (read s)
sumN :: Int -> Writer String Int sumN 0 = writer (0, "finish") sumN n = do   tell (show n ++ ",")
s <- sumN (n-1)
return (n + s)
ghci> sumN 5 WriterT (Identity (15,"5,4,3,2,1,finish"))
ghci> runWriter (sumN 5) (15,"5,4,3,2,1,finish")
cartesianProduct  :: [Int] -> [Int] -> [(Int, Int)] cartesianProduct xs ys = do   x <- xs
y <- ys
return (x, y)
ghci> cartesianProduct [1..2] [1..3] [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]
(>>=) :: Monad m => m a -> (a -> m b) -> m b
(>>) :: Monad m => m a -> m b -> m b

Folding and traversing

The last two classes are Foldable and Traversable—both of them capture the idea of processing a container, a collection of values, with different possibilities.

class Foldable (t :: * -> *) where   foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b ...
class (Functor t, Foldable t) => Traversable (t :: * -> *) where   traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
sequenceA :: Applicative f => t (f a) -> f (t a)
mapM :: Monad m => (a -> m b) -> t a -> m (t b)
sequence :: Monad m => t (m a) -> m (t a)
{-# MINIMAL traverse | sequenceA #-}
addNumber :: Int -> IO String
addNumber n = pure (++) <*> pure (show n ++ " ") <*> getLine
ghci> traverse addNumber [1..5] aaa bbb ccc ddd eee
["1 aaa","2 bbb","3 ccc","4 ddd","5 eee"]
ghci> :t traverse addNumber [1..5] traverse addNumber [1..5] :: IO [String]
(a   -> f  b)      -> t a   -> f  (t b)
(Int -> IO String) -> [Int] -> IO [String]
traverse_  :: (Applicative f, Foldable t) => (a -> f b) -> t a -> f ()

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Manning Publications

Follow Manning Publications on Medium for free content and exclusive discounts.