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, (<>)

(<>) :: 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

  • 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

  • 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

  • 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

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.