101companies

Concept:

State monad

Headline

A monad for state

Illustration

Let us put to work the State monad in a simple interpreter.

A baseline interpreter

There are these expression forms: 

-- Simple Boolean expressions
data Expr = Constant Bool | And Expr Expr | Or Expr Expr
  deriving (Eq, Show, Read)

For instance, the following expression should evaluate to true: 

sample = And (Constant True) (Or (Constant False) (Constant True))

Here is a simple interpreter, indeed: 

-- A straightforward interpreter
eval :: Expr -> Bool
eval (Constant b) = b
eval (And e1 e2) = eval e1 && eval e2
eval (Or e1 e2) = eval e1 || eval e2

Adding counting to the interpreter

Now suppose that the interpreter should keep track of the number of operations applied. We count And and Oras operations. Thus, the sample term should count as 2. We may incorporate counting into the initial interpreter by essentially maintaing an extra result component for the counter. (We could also synthesize the count as output; see the illustration of the writer monad.)

To make the example a bit more interesting, let's add a construct Hide. The expectation is that operations under Hide are not counted. 

data Expr
  = Constant Bool
  | And Expr Expr
  | Or Expr Expr
  | Hide Expr

Because of the use of Hide, we would count 2 instead of 3 operations in the following term: 

sample =
  And
    (Constant True)
    (Or
      (Constant True)
      (Hide (And
        (Constant False)
        (Constant False))))

Here is the interpreter which incorporates counting: 

-- Interpreter with counting operations
eval' :: Expr -> Int -> (Bool, Int)
eval' (Constant b) i = (b, i)
eval' (And e1 e2) i = 
  let 
   (b1,i') = eval' e1 i
   (b2,i'') = eval' e2 i'
  in (b1 && b2, i''+1) 
eval' (Or e1 e2) i = 
  let 
   (b1,i') = eval' e1 i
   (b2,i'') = eval' e2 i'
  in (b1 || b2, i''+1) 
eval' (Hide e) i = (fst (eval' e i), i)

Alas, the resulting interpreter is harder to understand. The threading of counts is entangled with the basic logic.

Monadic style

By conversion to monadic style, we can hide counting except when we need increment the counter. We use the State monad here so that we really track the operations counter along evaluation; this would be useful if we were adding an expression form for retrieving the count. We could also be using the writer monad, if we were only interested in the final count. 

-- Monadic style interpreter
evalM :: Expr -> State Int Bool
evalM (Constant b) = return b
evalM (And e1 e2) = 
  evalM e1 >>= \b1 ->
  evalM e2 >>= \b2 ->
  modify (+1) >> 
  return (b1 && b2)
evalM (Or e1 e2) = 
  evalM e1 >>= \b1 ->
  evalM e2 >>= \b2 ->
  modify (+1) >> 
  return (b1 || b2)
evalM (Hide e) =
  get >>= \i ->
  evalM e >>= \b ->
  put i >>= \() ->
  return b

We can also use do notation: 

-- Monadic style interpreter in do notation
evalM' :: Expr -> State Int Bool
evalM' (Constant b) = return b
evalM' (And e1 e2) = do
  b1 <- evalM' e1
  b2 <- evalM' e2
  modify (+1)
  return (b1 && b2)
evalM' (Or e1 e2) = do
  b1 <- evalM' e1
  b2 <- evalM' e2
  modify (+1)
  return (b1 || b2)
evalM' (Hide e) = do
  i <- get
  b <- evalM e
  put i
  return b

The State monad

The state monad is readily provided by the Haskell library (in Control.Monad.State.Lazy), but we may want to understand how it might have been implemented. The data type for the State monad could look like this: 

-- Data type for the State monad
newtype State s a = State { runState :: s -> (a,s) }

Thus, a stateful computation is basically a function on state which also returns a value.

The corresponding instance of the type class Monad follows: 

-- Monad instance for State
instance Monad (State s)
  where
    return x = State (\s -> (x, s))
    c >>= f = State (\s -> let (x,s') = runState c s in runState (f x) s')

The definition of return conveys that a pure computation preserves the state. The definition of bind conveys that the state is to be threaded from the first argument to the second. Finally, we need to define state-specific operations: 

-- Important State operations: get/put state
get :: State s s
get = State (\s -> (s, s))

put :: s -> State s ()
put s = State (\_ -> ((), s))

-- Composition of get and put
modify :: (s -> s) -> State s ()
modify f = do { x <- get; put (f x) }

In modern Haskell, we also need to make State an instance of Applicative (for applicative functors and Functor (for functors). This code is omitted here, but see GitHub for this page.

Concept:

Functor

Headline

A functional programming idiom for mapping over containers

Illustration

The term "functor" originates from category theory, but this will be of no further concern in this description. In functional programming, "functor" refers to a programming idiom for mapping over contains or compound data. Functors have been popularized by Language:Haskell.

In Haskell, functors are programmed and used with the help of the type class Functor which is parametrized by a type constructor for the actual container type: 

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

The type constructor parameter f is the placeholder for the actual container type. The fmap function (for "functorial map") is the principle operation of a functor: parametrized by a function for mapping container elements of type a to elements of type b, it provides a mapping at the level of the container types, from f a to f b. Algebraically, the following properties are required for any functor (given in Haskell notation): 

fmap id = id
fmap f . fmap g = fmap (f . g)

The following Functor instance turns lists into a functor: 

instance Functor []
  where
    fmap = map

Thus, the folklore map function for list processing is a particular example of the notion of functorial map.

Here is another Functor instance turning the Maybe type constructor into a functor. 

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

See also the concept of rose trees for more complicated examples of functors.

Concept:

Monad

Headline

A functional programming idiom for computing effects

Illustration

The term "monad" originates from category theory, but this illustration focuses on the functional programming view where "monad" refers to a programming idiom for composing computations, specifically computations that may involve side effects or I/O actions. Monads have been popularized by Language:Haskell.

In Haskell, monads are developed and used with the help of the type class Monad which is parametrized by a type constructor for the actual monad. Here is a sketch of the type class: 

class Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  -- ... some details omitted

The return function serves the construction of trivial computations, i.e., computations that return values. The >>= (also knows as the bind function) compose a computation with a function that consumes the value of said computation to produce a composed computation. Here are some informal descriptions of popular monads:

  • State monad
    • return v: return value v and pass on state
    • bind c f: apply computation c as state transformer and pass on transformed state to f
  • Reader monad
    • return v: return value v and ignore environment
    • bind c f: pass environment to both c and f
  • Writer monad
    • return v: return value v and empty output
    • bind c f: compose output from both c and f
  • Maybe monad
    • return v: return "successful" value v
    • bind c f: fail if c fails, otherwise, pass on successful result to f

Concept:

Writer monad

Headline

A monad for synthesizing results or output

Illustration

Let us put to work the writer monad in a simple interpreter.

A baseline interpreter

There are these expression forms: 

-- Simple Boolean expressions
data Expr = Constant Bool | And Expr Expr | Or Expr Expr
  deriving (Eq, Show, Read)

For instance, the following expression should evaluate to true: 

-- A sample term with two operations
sample = And (Constant True) (Or (Constant False) (Constant True))

Here is a simple interpreter, indeed: 

-- A straightforward interpreter
eval :: Expr -> Bool
eval (Constant b) = b
eval (And e1 e2) = eval e1 && eval e2
eval (Or e1 e2) = eval e1 || eval e2

Adding counting to the interpreter

Now suppose that the interpreter should also return the number of operations applied. We count And and Oras operations. Thus, the sample term should count as 2. We may incorporate counting into the initial interpreter as follows: 

-- Interpreter with counting operations
eval' :: Expr -> (Bool, Int)
eval' (Constant b) = (b, 0)
eval' (And e1 e2) = 
  let 
   (b1,i) = eval' e1
   (b2,i') = eval' e2
  in (b1 && b2, i+i'+1) 
eval' (Or e1 e2) = 
  let 
   (b1,i) = eval' e1
   (b2,i') = eval' e2
  in (b1 || b2, i+i'+1)

Alas, the resulting interpreter is harder to understand. The collection of counts is entangled with the basic logic.

Monadic style

By conversion to monadic style, we can hide counting except when we need increment the counter. We use the Writer monad here so that we simply combine counts from subexpression (as also done in the non-monadic code above). We could also be using the state monad, if we wanted to really track the operations counter along evaluation; this would be useful if we were adding an expression form for retrieving the count. 

evalM :: Expr -> Writer (Sum Int) Bool
evalM (Constant b) = return b
evalM (And e1 e2) = 
  evalM e1 >>= \b1 ->
  evalM e2 >>= \b2 ->
  tell (Sum 1) >> 
  return (b1 && b2)
evalM (Or e1 e2) = 
  evalM e1 >>= \b1 ->
  evalM e2 >>= \b2 ->
  tell (Sum 1) >> 
  return (b1 || b2)

We can also use do notation: 

-- Monadic style interpreter in do notation
evalM :: Expr -> Writer (Sum Int) Bool
evalM (Constant b) = return b
evalM (And e1 e2) = do
  b1 <- evalM e1
  b2 <- evalM e2
  tell (Sum 1)
  return (b1 && b2)
evalM (Or e1 e2) = do
  b1 <- evalM e1
  b2 <- evalM e2
  tell (Sum 1)
  return (b1 || b2)

The Writer monad

The Writer monad is readily provided by the Haskell library (in Control.Monad.Trans.Writer.Lazy), but we may want to understand how it might have been implemented. The data type for the Writer monad could look like this: 

-- Computations as pairs of value and "output"
newtype Writer w a = Writer { runWriter :: (a, w) }

Thus, a stateful computation is basically a function a value with some output. The output type is assumed to be monoid because an empty output and the combination of outputs is uniformly defined in this manner.

The corresponding instance of the type class Monad follows: 

-- Monad instance for Writer
instance Monoid w => Monad (Writer w)
  where
    return a = Writer (a, mempty)
    (Writer (a, w)) >>= f =
      let (Writer (b, w')) = f a in
        (Writer (b, w `mappend` w'))

The definition of return conveys that a pure computation produces the empty output. The definition of bind conveys that outputs are to be combined (in a certain order) from the operands of bind. Finally, we need to define the writer-specific operation tell for producing ouput: 

-- Produce output
tell :: w -> Writer w ()
tell w = Writer ((), w)

In modern Haskell, we also need to make Writer an instance of Applicative (for applicative functors and Functor (for functors). This code is omitted here, but see GitHub for this page.

See Contribution:haskellWriter for a contribution which uses the writer monad.

Concept:

Type class

Headline

An abstraction mechanism for bounded polymorphism

Illustration

Type classes are not to be confused with OO classes. In fact, type classes may be somewhat compared with OO interfaces. Type classes have been popularized by Haskell. Similar constructs exist in a few other languages. Type classes capture operations that may be defined for many types. The operations can be defined differently for each type, i.e., for each instance of a type class.

All subsequent illustrations leverage Haskell. Let us consider the following datatypes of bits and bitstreams which represent unsigned binary numbers. We are going to enrich these datatypes with some functionality eventually, with the help of type classes: 

-- A bit can be zero or one
data Bit = Zero | One

-- Bit streams of any length
newtype Bits = Bits { getBits :: [Bit] }

Thus, the binary number "101" would be represented as follows: 

Bits [One,Zero,One]

Now suppose that we want to define some standard operations for bits and bitstreams: equality, total order, unparsing to text, parsing from text, and possibly others. Let us begin with unparsing (conversion) to text. To this end, we should implement Haskell's type-class-polymorphic function show so that it produces text like this: 

> show (Bits [One,Zero,One])
"101"

Here is the type class Show which declares indeed the polymorphic show function: 

class Show a
  where
    show :: a -> String

In reality, the type class has not just one member, show, as shown, but we omit the discussion of the other members here for brevity. The type class is parameterized in a type a for the actual type for which to implement the members. Here are the type-class instances for bits and bit streams: 

-- Show bits
instance Show Bit 
  where
    show Zero = "0"
    show One = "1"

-- Show bit streams
instance Show Bits
  where
    show = concat . map show . getBits

Thus, the instance fills the position of the type parameter with an actual type such as Bit and Bits. Also, the member function show is actually defined, while assuming the specific type. We show a bit as either "0" or "1". We show a bit stream by showing all the individual bits and concatenating the results.

The inverse of show is read. There is also a corresponding type class Read, which we skip here for brevity. Let us consider equality instead. There is again a type class which captures the potential of equality for many types: 

class Eq a
  where 
    (==) :: a -> a -> Bool

The member "(==)" is the infix operation for testing two bit streams to be equal. Arguably, bit streams are equal, if they are of the same length and they agree on each other bit by bit. In fact, the following definition is a bit more general in that it also trims away preceding zero bits: 

-- Test bits for equality
instance Eq Bit
  where
    Zero == Zero = True
    Zero == One = False
    One == One = True
    One == Zero = False

-- Test bit streams for equality
instance Eq Bits
  where
    x == y =  length x' == length y'
           && and (map (uncurry (==)) (zip x' y'))
      where
        x' = trim (getBits x)
        y' = trim (getBits y)
        trim [] = []
        trim z@(One: ) = z
        trim (Zero:z) = trim z

For instance: 

-- Test bit streams for equality
> let b101 = read "101" :: Bits
> let b0101 = read "0101" :: Bits
> let b1101 = read "1101" :: Bits
> b101 == b0101
True
> b101 == b1101
False

Actually, bit streams are (unsigned) binary numbers. Thus, we should also instantiate the corresponding type classes for number types. Operations on number types are grouped in multiple type classes. The type class Num deals with addition, subtraction, multiplication, and a few other operations, but notably no division: 

class (Eq a, Show a) => Num a
  where
    (+) :: a -> a -> a
    (*) :: a -> a -> a
    (-) :: a -> a -> a
    negate :: a -> a
    abs :: a -> a
    signum :: a -> a
    fromInteger :: Integer -> a

We would like to instantiate the Num type class for bit streams. There are different ways of doing this. For instance, we could define addition by bitwise addition, right at the level of bit streams, or we could instead resort to existing number types. For simplicity, we do indeed conversions from and to Integer, in fact, any integral type: 

-- Convert bits to an integer
bits2integral :: Integral a => Bits -> a
bits2integral = foldl f 0 . getBits 
  where
    f a b = a * 2 + (bit2int b)
    bit2int Zero = 0
    bit2int One = 1

-- Convert a (non-negative) integral to bits
integral2bits :: Integral a => a -> Bits
integral2bits i | i < 0 = error "Bits are unsigned"
integral2bits i = Bits (f [] i)
  where
    f xs 0 = xs
    f xs i = f (x:xs) (i `div` 2) 
      where
        x = if odd i then One else Zero

On these grounds, we can trivially instantiate the Num type class for Bits by simply reusing the existing instance for Integer through systematic conversions. 

-- Bits as a Num type
instance Num Bits
  where
    x + y = integral2bits z'
      where
        x' = bits2integral x
        y' = bits2integral y
        z' = x' + y'
    x * y = integral2bits z'
      where
        x' = bits2integral x
        y' = bits2integral y
        z' = x' * y'
    x - y = integral2bits z'
      where
        x' = bits2integral x
        y' = bits2integral y
        z' = x' - y'
    abs = id
    signum = integral2bits
           . signum
           . bits2integral
    fromInteger = integral2bits

The examples given so far are concerned with predefined type classes. However, type classes can also be declared by programmers in their projects. Let's assume that we may need to convert data from different formats into ``Ints. Here is a corresponding type class with a few instances: 

class ToInt a
  where
    toInt :: a -> Maybe Int

instance ToInt Int
  where
    toInt = Just

instance ToInt Float
  where
    toInt = Just . round

instance ToInt String
  where
    toInt s =
      case reads s of
        [(i, "")] -> Just i
        _ -> Nothing

The conversion can be illustrated like this: 

*Main> toInt "5"
Just 5
*Main> toInt "foo"
Nothing
*Main> toInt (5::Int)
Just 5
*Main> toInt (5.5::Float)
Just 6

In Haskell, type-class parameters are not limited to types, but, in fact, type classes may be parameterized in type constructors. Consider the following type class which models different notions of size for container types: 

-- Notions of size for container types
class Size f
  where
    -- Number of constructors
    consSize :: f a -> Int
    -- Number of elements
    elemSize :: f a -> Int

Here is a straightforward instance for lists: 

instance Size []
  where
    consSize = (+1) . length
    elemSize = length

Let's also consider sizes for rose trees: 

-- Node-labeled rose trees
data NLTree a = NLTree a [NLTree a]
  deriving (Eq, Show, Read)

instance Size NLTree
  where
    consSize (NLTree _ ts) =
        1
      + consSize ts
      + sum (map consSize ts)
    elemSize (NLTree _ ts) =
        1
      + sum (map elemSize ts)

-- Leaf-labeled rose trees
data LLTree a = Leaf a | Fork [LLTree a]
  deriving (Eq, Show, Read)

instance Size LLTree
  where
    consSize (Leaf _) = 1
    consSize (Fork ts) =
        consSize ts
      + sum (map consSize ts)
    elemSize (Leaf _) = 1
    elemSize (Fork ts) =
      sum (map elemSize ts)

A few illustrations are due: 

*Main> let list = [1,2,3]
*Main> let nltree = NLTree 1 [NLTree 2 [], NLTree 3 []]
*Main> let lltree = Fork [Leaf 1, Fork [Leaf 2, Leaf 3]]
*Main> consSize list
4
*Main> elemSize list
3
*Main> consSize nltree 
8
*Main> elemSize nltree 
3
*Main> consSize lltree 
9
*Main> elemSize lltree 
3

Concept:

State

Headline

The state of a program or system

Synonyms

  • Program state

Concept:

Applicative functor

Headline

A functor with function application within the functor

Description

Applicative functors are described here briefly in Haskell's sense.

The corresponding type class (modulo some simplifications) looks as follows. 

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

The expectation is that pure promotes a value to a functorial value whereas "<*>" can be seen as a variation of fmap such that a function within the functor (as opposed to just a plain function) is applied to a functorial value.

The following laws are assumed. 

pure f <*> x = fmap f x
pure id <*> v = v
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
pure f <*> pure x = pure (f x)
u <*> pure y = pure ($ y) <*> u

Illustration

Simple examples

We make Maybe and lists applicative functors: 

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

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

Thus, in the Maybe case, a Nothing as a function makes us return a Nothing as result, but if the function is available then it is fmapped over the argument. In the list case, we use a list comprehension to apply all available functions too all available values.

The instances can be exercised at the Haskell prompt as follows: 

> Just odd <*> Just 2
Just False
> [odd, even] <*> [1,2,3,4]
[True,False,True,False,False,True,False,True]

To see that applicative functors facilitate function application for functorial values pretty well, consider the following functorial variation on plain function application. 

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

Consider the following application. 

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

Thus, the applicative operator "<*>" is used to line up (any number of) functorial arguments and fmap is used for the "rest" of the application.

A more advanced example

We will use now an applicative functor to support environment passing within a recursive computation.

Consider the following interpreter for simple expressions: 

data Exp
  = Var String
  | Val Int
  | Add Exp Exp

-- Environments with a fetch (lookup) function
type Env = [(String, Int)]
fetch x ((y,v):n) = if x==y then v else fetch x n

-- Straightforward interpreter; we take care of environment passing
eval :: Exp -> Env -> Int
eval (Var x) n = fetch x n
eval (Val v) _ = v
eval (Add e1 e2) n = eval e1 n + eval e2 n

We can evaluate expressions like this: 

> eval (Add (Var "x") (Val 22)) [("x", 20)]
42

Let's try to switch to a more combinatorial style such that we abstract from explicit environment passing. To this end, we leverage the so-called SKI combinators: 

-- More point-free, combinatorial interpreter hiding some environment passing
eval' :: Exp -> Env -> Int
eval' (Var x) = fetch x
eval' (Val v) = k v
eval' (Add e1 e2) = k (+) `s` eval' e1 `s` eval' e2

-- https://en.wikipedia.org/wiki/SKI_combinator_calculus
i :: a -> a
i x = x -- aka id
k :: a -> b -> a
k x y = x -- aka const
s :: (a -> b -> c) -> (a -> b) -> a -> c
s x y z = x z (y z) -- aka <*> of applicative

The applicative functor for the instance "(->) a" provides exactly the necessary abstraction: 

-- Switch to applicative functor style, thereby demonstrating a general pattern
eval'' :: Exp -> Env -> Int
eval'' (Var x) = fetch x
eval'' (Val v) = pure v
eval'' (Add e1 e2) = pure (+) <*> eval'' e1 <*> eval'' e2