Take a walk on the functional side: yes, we need monads

Apr 6, 2024

It’s not always practical to rewrite a large codebase in a functional language. But it’s natural for a large codebase, especially in finance, to have a functional core, as functional programming is a natural fit to express data transformations. We can use functional programming techniques to improve the quality and maintainability of our code. Even for Python-exclusive projects, I often require my team to write core functions in a functional style (a quant module). Following SOLID principles, we can write core functions that are small, single-purpose, and pure, which makes them easier to test and reason about. The rest of the codebase can then be written in an imperative style, calling these core functions as needed.

In this post, I’ll provide some insights into incorporating elements of functional programming into a large imperative codebase, using Haskell and Python as an example. I assume you are a professional developer with a basic understanding of functional programming concepts.

We often refer to the term functional programming, meaning the following programming techniques:

Some other not necessarily exclusive features of functional programming languages include:

Syntax

Composition

g :: X -> Y
f :: Y -> Z
f . g :: X -> Z

Note the composition order. By default A -> B -> C means A -> (B -> C). If you want to describe the type (A -> B) -> C, you need the parentheses.

Guarded equations

abs:: Float -> Float
abs n | n >= 0     =  n
      | otherwise  = -n

bmiClassifier :: (Fractional a, Ord a) => a -> a -> String
bmiClassify weight height
   | bmi <= 18.5 = "underweight"
   | bmi <= 25.0 = "normal"
   | bmi <= 30.0 = "overweight"
   | otherwise   = "obese"
where bmi = weight / height ^ 2

The first arrow (=>) separates the type constraints (here, (Fractional a, Ord a)) from the rest of the type signature. In Haskell, all functions are considered to be curried by default. This means that a function that takes multiple arguments is actually a series of functions, each taking a single argument and returning another function (except for the final function, which returns the result). This currying is a fundamental aspect of how functions are represented and applied in Haskell, leading to its characteristic arrow-heavy type signatures.

Pattern matching

sumList :: Num a => [a] -> a
sumList xs = case xs of
    []      -> 0
    (x:xs') -> x + sumList xs'

In recursion, the base case is the empty list [], and the recursive case is (x:xs'). The colon : is the list constructor, which separates the head x from the tail xs'. The base case returns 0, and the recursive case returns the sum of the head x and the sum of the tail sumList xs'.

In Haskell, the apostrophe (') in the variable name xs' (pronounced “exs prime”) doesn’t have a special syntactic meaning; it’s simply part of the variable name. Haskell allows apostrophes in identifiers, and they are often used by Haskell programmers to denote a related or modified version of a variable. In this context, xs’ is a new list derived from the original list xs by removing its head element.

describeList :: [a] -> String
describeList xs = case xs of
  []  -> "The list is empty."
  [x] -> "The list has one element."
  xs  -> "The list has multiple elements."

You can also write in a direct pattern matching style:

sumList :: Num a => [a] -> a
sumList [] = 0                    -- Base case: the sum of an empty list is 0
sumList (x:xs) = x + sumList xs   -- Recursive case: add the head to the sum of the tail

bmiClassifier weight height = case () of
  _ | bmi <= 18.5 -> "underweight"
    | bmi <= 25.0 -> "normal"
    | bmi <= 30.0 -> "overweight"
    | otherwise   -> "obese"
  where bmi = weight / height ^ 2

bmiClassifier weight height =
  let bmi = weight / height ^ 2
  in case () of
       _ | bmi <= 18.5 -> "underweight"
         | bmi <= 25.0 -> "normal"
         | bmi <= 30.0 -> "overweight"
         | otherwise   -> "obese"

The unit value is denoted by () and is the only value of the unit type, also written as (). The unit type and value are somewhat analogous to void in other programming languages, but with some key differences due to Haskell’s purely functional nature.

printMessage :: String -> IO ()
printMessage msg = putStrLn msg

In Haskell, the underscore (_) is used as a wildcard pattern that matches anything without binding it to a variable. In the context of your code snippet, the underscore is used in a somewhat unconventional but perfectly valid way to facilitate a case expression that’s solely used to enable pattern guards for expressing conditional logic. This technique is a bit of a Haskell idiom for structuring code that depends on multiple conditions.

-- also works
bmiClassifier :: (RealFloat a) => a -> a -> String
bmiClassifier weight height =
  if bmi <= 18.5 then "underweight"
  else if bmi <= 25.0 then "normal"
  else if bmi <= 30.0 then "overweight"
  else "obese"
  where bmi = weight / height ^ 2

let Floating

Let floating is an optimization technique where let bindings are moved (“floated”) to a different scope. This can be done to either:

Move computations closer to where they are used (floating inwards), to avoid unnecessary computation in code paths where the values are not used. Move computations to a common scope (floating outwards) where multiple branches of code can share the result, to avoid redundant computation.

without let floating
calculate :: Int -> Int -> Int
calculate x y =
  if x > 10
    then let a = x * 2
         in a + y
    else let a = x * 3
         in a - y

-- with let floating
calculate :: Int -> Int -> Int
calculate x y =
  let a = if x > 10 then x * 2 else x * 3
  in if x > 10 then a + y else a - y

Lambda lifting

Lambda lifting is a transformation that converts local function definitions into top-level functions. This transformation is useful for making functions available to other functions that need them, and for improving code readability by separating concerns.

-- without lambda lifting
outerFunction x y =
  let
    innerFunction z = x + y + z
  in
    innerFunction 10

-- with lambda lifting
innerFunction x y z = x + y + z
outerFunction x y = innerFunction x y 10

in practice, lambda lifting is part of the compilation process for functional languages and is handled automatically by the compiler.

Conventions

Syntax differences against Python

Operators

a && b returns the boolean value True if both a and b do, and False otherwise.

(&&) :: Bool -> Bool -> Bool
(||) :: Bool -> Bool -> Bool
(++) :: [a] -> [a] -> [a]

Infix operators

We can declare new operators easily; for example:

(+++) :: Int -> Int -> Int
x +++ y = if even x then y else x + y

Indexing

List-indexing operation (!!). Given a list xs and an index n, the expression xs!!n returns the element of xs at position n, counting from 0.

Quotes

Single quotes means single character, double quotes means character array (string). In Haskell, 'c' is a single character ( Char ), and "c" is a list of characters ( [Char] ).

Lambda expressions

A lambda expression \n -> 2*n+1. This is equivalent to the Python lambda expression lambda n: 2*n+1.

Indentation vs braces

This is sort of a mess in Haskell. You can use indentation or braces and semicolons to separate blocks of code.

Code which is part of some expression should be indented further in than the beginning of that expression (even if the expression is not the leftmost element of the line).

main :: IO ()
main = do {
    putStrLn "What is your name?";
    name <- getLine;
    putStrLn $ "Hello, " ++ name ++ "!"
}

-- also works
main :: IO ()
main = do
    putStrLn "What is your name?"
    name <- getLine
    putStrLn $ "Hello, " ++ name ++ "!"

roots :: (Float,Float,Float) -> (Float,Float)
roots (a,b,c)
| a == 0 = error "not quadratic"
| disc < 0 = error "complex roots"
| otherwise = ((-b-r)/e, (-b+r)/e)
where {disc = b*b - 4*a*c; r = sqrt d; e = 2*a}

-- also works
where disc = b*b - 4*a*c
      r = sqrt d
      e = 2*a

-- but not
where disc = b*b - 4*a*c
         r = sqrt d
         e = 2*a

Strictness

A Haskell function f is said to be strict if f undefined = undefined, and nonstrict otherwise.

Data structures

Lists

We can have lists over any type but we cannot mix different types in the same list. The operator (:) :: a -> [a] -> [a], pronounced ‘cons’, is a constructor for lists.

In Haskell, data types are used to define the structure and representation of data in a program. They allow you to create custom types to suit the needs of your application.

data Person = Person { name :: String, age :: Int }

alice :: Person
alice = Person { name = "Alice", age = 30 }

In particular, the data type for List is defined as:

data List a = Nil | Cons a (List a)

This definition is a recursive data type, where Nil represents an empty list and Cons represents a list with a head element of type a and a tail that is another list of type a.

List notation, such as [1,2,3], is in fact an abbreviation for a more basic form 1:2:3:[].

As a result of above:

iterate is a function in Haskell that generates an infinite list by repeatedly applying a function to a starting value. Its type signature is:

iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)

The function map then applies f to each element of the list [x1, x2, ..., xn], producing a new list [f x1, f x2, ..., f xn] of type [b].

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs st

Enumerations

Cool tricks over lists of integers. As a matter of fact, enumerations are not restricted to integers, but to members of yet another type class Enum

[1..10] -- [1,2,3,4,5,6,7,8,9,10]
[1,3..10] -- [1,3,5,7,9]
[1..] -- infinite list
['a'..'z'] -- "abcdefghijklmnopqrstuvwxyz"
['a'..'z'] ++ ['A'..'Z'] -- "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

Successor and predecessor

succ :: Enum a => a -> a
pred :: Enum a => a -> a

succ 5 -- 6
pred 5 -- 4

List comprehensions

List comprehensions are a way to generate lists in Haskell by specifying a predicate and a set of generators. The syntax is similar to set builder notation in mathematics.

[x^2 | x <- [1..5]] -- [1,4,9,16,25]
[(x,y) | x <- [1,2], y <- [3,4]] -- [(1,3),(1,4),(2,3),(2,4)]

-- Pythagorean triples
triads :: Int -> [(Int,Int,Int)]
triads n = [(x,y,z) | x <- [1..n], y <- [1..n],
    z <- [1..n], x*x+y*y==z*z]

triads 10 -- [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]

-- divisors
divisors x = [d | d <- [2..x-1], x `mod` d == 0]

divisors 12 -- [2,3,4,6]

-- coprime
coprime x y= disjoint (divisors x) (divisors y)

coprime 12 25 -- True

import qualified Data.Set as Set

-- Define two sets
let setA = Set.fromList [1, 2, 3]
let setB = Set.fromList [4, 5, 6]

-- Check if disjoint (i.e., their intersection is empty)
let disjoint = Set.null (Set.intersection setA setB)

Functors

Functor is a type class that represents types that can be mapped over. The fmap function is used to apply a function to the elements of a functor.

Functor laws of maps are:

map id = id
map (f . g) = map f . map g

Rename the type of the function to fmap:

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

One of the simplest examples of a functor in Haskell is the Maybe type, which is used to represent values that might be missing. The Maybe type is defined as:From experience, most Python bugs in production are caused by careless handling of None and exceptions – this is in a way encouraged by Python by virtue of being a dynamic language. You essentially are tolerating leaky code that break in production in unexpected ways. If you want to have a more pleasant computational infrastructure, I don’t think you can get around without implementing a Maybe monad (to get around None that’s plaguing your code) or introducing exceptionless programming patterns in Python. In other words, implement monads (see below). 

data Maybe a = Nothing | Just a

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

main = do
  print $ fmap (*2) (Just 100)    -- Outputs: Just 200
  print $ fmap (*2) Nothing       -- Outputs: Nothing
  print $ fmap show (Just 123)    -- Outputs: Just "123"

-- A function that might fail to return a value
safeDivide :: Int -> Int -> Maybe Int
safeDivide _ 0 = Nothing  -- Division by zero is not allowed
safeDivide x y = Just (x `div` y)

-- Using `Maybe` values
example1 :: Maybe Int
example1 = Just 5

example2 :: Maybe Int
example2 = safeDivide 10 0  -- This will be Nothing

example3 :: Maybe Int
example3 = safeDivide 10 2  -- This will be Just 5

-- Pattern matching on `Maybe` values
printMaybe :: Show a => Maybe a -> String
printMaybe Nothing = "No value"
printMaybe (Just x) = "The value is " ++ show x

main :: IO ()
main = do
  putStrLn $ printMaybe example1  -- Outputs: The value is 5
  putStrLn $ printMaybe example2  -- Outputs: No value
  putStrLn $ printMaybe example3  -- Outputs: The value is 5

zip and zipWith

zip :: [a] -> [b] -> [(a,b)]
zip (x:xs) (y:ys) = (x,y): zip xs ys
zip _ _ = []

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (x:xs) (y:ys)=fxy: zipWith f xs ys
zipWith f _ _ = []

-- zipWith is cool - we should have it in Python

main = print $ zipWith (+) [1, 2, 3] [4, 5, 6]
-- Output: [5, 7, 9]

main = print $ zipWith (\x y -> x * 2 + y) [1, 2, 3] [4, 5, 6]
-- Output: [6, 9, 12]

main = print $ zipWith (\c n -> replicate n c) ['a', 'b', 'c'] [1, 2, 3]
-- Output: ["a","bb","ccc"]

Some key points to note about the type signature of zipWith:

But when you read (a -> b -> c), you should think a function that takes two arguments of types a and b and returns a value of type c.

Higher-order functions

($): Function application operator

It is used to apply a function to an argument. It’s useful for reducing the need for parentheses because it has low, right-associative precedence.

($) :: (a -> b) -> a -> b

-- Without $
print (sum (filter (> 10) (map (*2) [1..10])))

-- With $
print $ sum $ filter (> 10) $ map (*2) [1..10]

This looks similar to the Unix pipe operator |, except for the direction of the flow. You can use infixl 0 |> declares the operator to be left-associative with a precedence level of 0, which is the same as $. x |> f = f x defines the operator such that x |> f is equivalent to f x.

infixl 0 |>
(|>) :: a -> (a -> b) -> b
x |> f = f x

--
result = [1, 2, 3, 4]
|> filter even
|> map (*2)
|> sum

filter

It takes a predicate and a list, returning a list of elements that satisfy the predicate.

filter :: (a -> Bool) -> [a] -> [a]

---
let evens = filter even [1..10]  -- evens is [2,4,6,8,10]

map

It applies a function to each element of a list, returning a new list of the results.

map :: (a -> b) -> [a] -> [b]
let squares = map (^2) [1..5]  -- squares is [1,4,9,16,25]

flip

In Haskell, flip is a higher-order function that takes a function as an input and returns a new function with its first two arguments swapped.

flip :: (a -> b -> c) -> b -> a -> c

-- Without flip
subtract :: Num a => a -> a -> a
subtract x y = x - y

-- With flip
subtract' :: Num a => a -> a -> a
subtract' = flip subtract

-- Example usage
result = subtract 10 5  -- Output: 5
result' = subtract' 10 5  -- Output: -5

foldr

foldr is a higher-order function that takes a binary function, an initial value, and a list, and applies the function to the elements of the list from right to left, starting with the initial value.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ e [] = e
foldr f e (x:xs) = f x (foldr f e xs)

--
foldr (@) e [x,y,z] = x @ (y @ (z @ e))
            [x,y,z] = x : (y : (z : []))

--
sumList :: [Int] -> Int
sumList = foldr (+) 0

from functools import reduce

# Mimic foldr by reversing the list first
def foldr(func, acc, lst):
    return reduce(func, reversed(lst), acc)

# Example usage
result = foldr(lambda x, y: x - y, 0, [1, 2, 3])
print(result)  # Output: 2, because it calculates ((1 - (2 - (3 - 0))) = 2

### also works
def foldr(func, acc, lst):
    if not lst:
        return acc
    else:
        return func(lst[0], foldr(func, acc, lst[1:]))

# Example usage
result = foldr(lambda x, y: x - y, 0, [1, 2, 3])
print(result)  # Output: 2

In Haskell, foldr1 is a variant of foldr that does not require an explicit starting value (accumulator). Instead, foldr1 uses the last element of the list as the starting value. This function is useful when you can assume the list is non-empty and the operation is associative and has an identity element, but you don’t need to specify it explicitly.

maxInList :: (Ord a) => [a] -> a
maxInList = foldr1 max

scanl

In Haskell, scanl is a function that is similar to foldl, but instead of returning a single final result, it returns an intermediate result at each step, producing a list of progressively reduced values. This can be particularly useful for seeing the evolution of the reduction process over each element of the input list.

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl f e = map (foldl f e) . inits
inits :: [a] -> [[a]]
inits [] = [[]]
inits (x:xs) = [] : map (x:) (inits xs)

--
runningMax :: (Ord a, Num a) => [a] -> [a]
runningMax = scanl1 max

calculateDrawdown :: (Fractional a) => a -> a -> a
calculateDrawdown maxSoFar price = (price - maxSoFar) / maxSoFar * 100

drawdownPercentage :: (Ord a, Fractional a) => [a] -> [a]
drawdownPercentage prices = zipWith calculateDrawdown (runningMax prices) prices

Imperative functional programming

The type IO a is an abstract type representing actions that interact with the outside world and produce a value of type a. The main function is the entry point of a Haskell program and has the type IO ().

An action is a function that takes a world and delivers a value of type a and a new world. The new world is then used as the input for the next action. Having changed the world with an input–output action, you can’t go back to the old world. You can’t duplicate the world or inspect its components. All you can do is operate on the world with given primitive actions, and put such actions together in a sequence.

putChar :: Char -> IO ()  -- write a character to the screen
putStr :: String -> IO ()  -- write a string to the screen
putStrLn :: String -> IO ()  -- write a string to the screen followed by a newline
print :: Show a => a -> IO ()  -- write a value to the screen followed by a newline
getChar :: IO Char  -- read a character from the keyboard
getLine :: IO String  -- read a line from the keyboard
return :: a -> IO a  -- return a value from an action

Bind operator

One simple operation to sequence actions is denoted by (>>) and has type

(>>) :: IO a -> IO b -> IO b

Given actions p and q, the action p >> q first performs action p and then performs action q. The value returned by p >> q is the value returned by q.

If you care about the value of the first action, you can use the >>= operator, which is pronounced “bind” and has the type:

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

-- A safe division function that fails (returns Nothing) if trying to divide by zero.
safeDivide :: Double -> Double -> Maybe Double
safeDivide _ 0 = Nothing
safeDivide x y = Just (x / y)

-- A function that adds 10 to the given number but fails if the result exceeds 100.
addTen :: Double -> Maybe Double
addTen x = if x + 10 > 100 then Nothing else Just (x + 10)

main :: IO ()
main = do
  -- Successful operation: 100 divided by 2 is 50, then 10 is added, resulting in 60.
  print $ Just 100 >>= safeDivide 2 >>= addTen

  -- Fails at division: 100 divided by 0 fails, so the entire computation results in Nothing.
  print $ Just 100 >>= safeDivide 0 >>= addTen

  -- Fails at addition: 100 divided by 1 is 100, then adding 10 would exceed 100, so it fails.
  print $ Just 100 >>= safeDivide 1 >>= addTen

Components of the type signature:

The bind operator (>>=) sequences two IO actions in such a way that the output of the first action is fed into the function that produces the second action. It’s how Haskell chains operations that have side effects, ensuring that the effects occur in the correct order.

Monads

The type IO a is an abstract type in the sense described in the previous chapter, so we are not told how its values, which are called actions or commands, are represented. But you can think of this type as being

type IO a = World -> (a,World)

where a World is a representation of the state of the world, and an action of type IO a is a function that takes a world and returns a value of type a and a new world. The new world is then used as the input for the next action. Having changed the world with an input–output action, you can’t go back to the old world. You can’t duplicate the world or inspect its components. All you can do is operate on the world with given primitive actions, and put such actions together in a sequence.

Monads are a fundamental concept in functional programming, particularly in Haskell, where they play a central role in handling side effects, managing state, dealing with exceptions, and more, in a pure functional way.

At their core, monads are a type of abstract data type that represent computations instead of data in the traditional sense. They can be thought of as “computation wrappers” that provide a context for the values they contain. This context can represent various things, such as the possibility of failure (as with Maybe), a side effect (as with IO), or a state (as with State).

In Haskell, a monadMonads provide a way to abstract and encapsulate computations and side effects in a pure functional language like Haskell. They allow for: Sequencing operations: Especially useful when each step depends on the outcome of the previous one. Handling failure: By encapsulating operations that might fail in a context that can be easily checked and managed. Managing side effects: Such as IO operations, in a controlled manner without breaking the purity of the functional paradigm. State management: Allowing for state to be threaded through computations in a controlled way. is represented by the Monad type class, which defines two essential operations: >>= (bind) and return.

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

Why Maybe monad is needed? The Maybe monad in Haskell serves several important purposes, particularly in handling operations that can fail or result in an absence of value. It encapsulates the concept of computations that might not return a value in a way that is both type-safe and expressive, avoiding some common pitfalls found in other programming paradigms, such as null pointer exceptions. Here’s a deeper look into why the Maybe monad is needed and beneficial:

1. Safe Handling of Absent Values In many programming languages, operations that can fail or produce no value are handled by returning null or a similar sentinel value. However, this approach can lead to errors such as null pointer exceptions if the absence of a value is not properly checked everywhere it’s used. The Maybe type makes the possibility of an absent value explicit in the type system, forcing the programmer to handle it. This leads to safer code by design.

2. Type Safety The Maybe monad wraps a value in either Just (indicating presence of a value) or Nothing (indicating absence), making it clear from the type signature which functions might not return a value. This explicitness integrates with Haskell’s type system, providing compile-time checks for potential runtime errors related to missing values. It’s a way to leverage the type system to ensure that code dealing with potentially absent values is written safely.

3. Composability Monads, including Maybe, provide a way to compose operations that might fail. Using the »= operator (bind), you can chain together multiple computations that return Maybe values without having to manually check for Nothing at each step. This leads to cleaner, more readable code by abstracting away the boilerplate of error checking and handling.

4. Functional Approach to Error Handling The Maybe monad represents a functional approach to error handling. Instead of using exceptions for control flow (which can be considered side effects and are not purely functional), Maybe encapsulates the presence or absence of a value as a result of a computation. This aligns with Haskell’s philosophy of pure functional programming, where functions are expected to return a value for every input and side effects are minimized.

5. Enhanced Expressiveness Using Maybe makes code more expressive by clearly indicating the intent and the possible outcomes of a function. For example, a function signature like findElement :: (a -> Bool) -> [a] -> Maybe a clearly communicates that findElement might not find an element that satisfies the predicate, and thus, might not return a value.

6. Integration with Other Functional Patterns > Maybe integrates well with other functional patterns and utilities in Haskell, such as pattern matching, higher-order functions, and other monads. It can be used with map, fold, and filter operations in a way that is consistent with functional programming principles, further enhancing code safety and readability.

Conclusion The Maybe monad addresses several issues related to error handling, absent values, and type safety in a functional programming context. By making the potential absence of a value explicit in the type system and providing a structured way to compose operations that might fail, Maybe helps create more reliable, readable, and maintainable Haskell programs.

It’s just a way to wrap a value in a container.

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

instance Monad Maybe where
    return x = Just x
    Nothing >>= f = Nothing
    Just x >>= f = f x

case lookup x alist of
    Nothing -> Nothing
    Just y -> case lookup y blist of
            Nothing -> Nothing
            Just z -> lookup z clist

do notation

In Haskell, do notation is a syntactic sugar that simplifies working with monadic operations by allowing you to write sequences of actions in a way that looks imperative, making it easier to read and write monadic code. It’s particularly useful when dealing with monads like IO, Maybe, Either, and stateful computations, among others.

do {p} = p
do {p;stmts} = p >> do {stmts}
do {x <- p;stmts} = p >>= \x -> do {stmts}

do
  a <- Just 10
  b <- Just 20
  return (a + b)

-- just a syntactic sugar for
Just 10 >>= \a ->
Just 20 >>= \b ->
return (a + b)

Under the hood, do notation is translated into a series of applications of the bind operator (>>=) and the >> operator (which is a variant of >>= that ignores the result of the first action). This translation process allows you to write code that appears to be executing step-by-step instructions, similar to imperative languages, while still retaining the functional nature and benefits of monads.

do
    a <- action1
    action2 a
    b <- action3
    action4 b

-- is equivalent to
action1 >>= \a ->
action2 a >>
action3 >>= \b ->
action4 b

Monad laws

Monads in Haskell must satisfy three main properties or laws: left identity, right identity, and associativity. These properties ensure that monads behave in a predictable manner when chaining operations together.

(p >>= return) = p
--
do {x <- p; return x} = do {p}
--
Just 42 >>= return = Just 42

(return x >>= f) = f x
--
do {y <- return x; f y} = do {f x}
--
return 3 >>= (\x -> Just (x + 100)) = Just 103

((p >>= f) >>= g) = p >>= (\x -> (f x >>= g))
--
do {y <- do {x <- p; f x}; g y}
= do {x <- p; do {y <- f x; g y}}
= do {x <- p; y <- f x; g y}
--
f x = Just (x + 1)
g x = Just (x * 2)
(Just 5 >>= f) >>= g = Just 12
Just 5 >>= (\x -> f x >>= g) = Just 12

The monad laws say nothing much more than that expressions involving return and (>>=) simplify in just the way one would expect.

Monad: from mathematical perspective

In category theory, a monad is a monoid in the category of endofunctors of some fixed category. Let \(C\) be a category. A monad in \(C\) consists of a functor \(T: C \rightarrow C\) and two natural transformations.

\[\begin{aligned} \eta & : 1_C \rightarrow T \\ \mu & : T^2 \rightarrow T \end{aligned}\]

These are required to fulfill the following conditions (sometimes called coherence conditions), such that the following diagrams commute:

\[\begin{aligned} \mu \circ T\mu &= \mu \circ \mu T \\ \mu \circ T\eta &= \mu \circ \eta T = 1_T \end{aligned}\]
diagrams diagrams2

\(\eta\) is called the unit of the monad, and \(\mu\) is called the multiplication of the monad.

For comparison, the return function in Haskell corresponds to the unit \(\eta\) in the mathematical definition of a monad, and the >>= operator corresponds to the multiplication \(\mu\).

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

instance Monad Maybe where
    return x = Just x
    Nothing >>= f = Nothing
    Just x >>= f = f x

In category theory, a Kleisli category is a category naturally associated to any monad \(T\). The objects of the Kleisli category are the objects of the original category, and a morphism from \(A\) to \(B\) in the Kleisli category is a morphism from \(A\) to \(TB\) in the original category. Given two morphisms \(f: A \rightarrow TB\) and \(g: B \rightarrow TC\) in the Kleisli category, their composition is given by the following diagram:

\[\begin{aligned} A & \xrightarrow{f} TB \xrightarrow{Tg} T^2C \xrightarrow{\mu} TC \end{aligned}\]
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
(f >=> g) x = f x >>= g

--
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
(f <=< g) x = g x >>= f

--
(p >>= f) = (id >=> f) p
-- that is,
(>>=) = flip (id >=>).

State monads

The State monad is a way to encapsulate stateful computations in Haskell in a purely functional manner. It allows you to thread state through a series of computations without explicitly passing the state around as a parameter. This can help simplify code that involves mutable state by making the state transitions explicit and composable.Not an exclusively functional feature – react, e.g., has a similar state management hook.

We start by considering a simpler monad, called State s, for manipulating an explicit state s. You can think of the type State s a as being

type State s a = s -> (a,s)

Specifically, as well as the monad operations return and (>>=), five other functions are provided for working with the state monad:

put :: s -> State s ()
get :: State s s
state :: (s -> (a,s)) -> State s a
runState :: State s a -> (s -> (a,s))
evalState :: State s a -> s -> a

import Control.Monad.State

-- Define a type alias for our State monad instance. In this case, our state is just an Int.
type Counter = State Int

-- A simple function to increment the counter.
increment :: Counter ()
increment = modify (+1)

-- A function to get the current value of the counter.
getCounter :: Counter Int
getCounter = get

-- A function that uses the State monad to increment the counter twice and then retrieve its value.
exampleUsage :: Counter Int
exampleUsage = do
    increment
    increment
    getCounter

main :: IO ()
main = print $ runState exampleUsage 0

State-thread monads

State-thread monads are a generalization of the State monad that allows you to thread multiple pieces of state through a computation. This can be useful when you need to manage and update multiple pieces of state independently within a single computation. Like state monads, state-thread monads provide a way to encapsulate stateful computations in a purely functional manner.

type ST s a = s -> (a,s)

The core difference is the type variable s cannot be instantiated to specific states, such as Seed or [Int]. Instead it is there only to name the state. Think of s as a label that identifies one particular state thread. All mutable types are tagged with this thread, so that actions can only affect mutable values in their own state thread.

The “thread” part is where things can get a bit confusing because it doesn’t refer to threads in the sense of concurrent programming. Instead, it refers to the way the ST monad “threads” state changes through a sequence of computations. You can think of it as “threading” a line (the state) through a series of beads (the computations), where each bead might change the shape or color of the thread but everything is done in a single, linear sequence, not in parallel or concurrently.

STRef s a is a type that represents a mutable reference to a value of type a, where s is a type parameter used to ensure that references cannot be used outside the ST monad in which they were created. Neat similarities with react: the main difference between useState() and useRef() is that useState() is used to manage a state that triggers a re-render when it changes while useRef() is used to store mutable values that do not trigger a re-render. 

newSTRef :: a -> ST s (STRef s a)
readSTRef :: STRef s a -> ST s a
writeSTRef :: STRef s a -> a -> ST s ()

Pure functional:

fibonacci :: [Integer]
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

fibN :: Int -> Integer
fibN n = fibonacci !! n

With STArray:

import Control.Monad.ST (ST, runST)
import Data.Array.ST (STArray, newArray, readArray, writeArray)
import Data.Array (elems)

fibST :: Int -> Integer
fibST n
  | n <= 0    = 0
  | otherwise = runST $ do
      arr <- newArray (0, n) 0 :: ST s (STArray s Int Integer)

      writeArray arr 0 0
      writeArray arr 1 1

      mapM_ (fillFib arr) [2..n]

      readArray arr n

fillFib :: STArray s Int Integer -> Int -> ST s ()
fillFib arr n = do
  a <- readArray arr (n - 1)
  b <- readArray arr (n - 2)
  writeArray arr n (a + b)

--
main :: IO ()
main = print $ fibST 10

Without STArray

The action repeatFor repeats an action a given number of times:

repeatFor :: Monad m => Int -> m a -> m ()
repeatFor n action = foldr (>>) (return ()) (replicate n action)

This version of repeatFor is a higher-order function that takes two arguments: an integer n and a monadic action action. It returns a new action that, when executed, performs the original action n times in sequence, discarding the results of each action, and ultimately returns a unit value ().

Signature breakdown:

Body breakdown:

Given an action and a count n, repeatFor constructs a composite action that, when executed, runs the given action n times in sequence. It starts from the end of the list of replicated actions, sequencing each action with the next using (>>) and ultimately sequencing the last action with return (), ensuring that the entire composite action returns a unit value (). This function is useful for repeating side-effectful actions a specific number of times in a monadic context, such as printing messages, modifying mutable state in a controlled manner, or sending requests in an IO context.

The repeatFor function can be defined as a simple wrapper around replicateM_, which repeats an action a given number of times. Here, n times repetition of the action act is desired:

import Control.Monad (replicateM_)
import Control.Monad.ST (ST, runST)
import Data.STRef (newSTRef, readSTRef, writeSTRef)

repeatFor :: Int -> ST s () -> ST s ()
repeatFor n act = replicateM_ n act

fibST :: Int -> ST s Integer
fibST n = do
  a <- newSTRef 0
  b <- newSTRef 1
  repeatFor n $ do
    x <- readSTRef a
    y <- readSTRef b
    writeSTRef a y
    writeSTRef b $! (x + y)
  readSTRef a

computeFib :: Int -> Integer
computeFib n = runST (fibST n)

main :: IO ()
main = print $ computeFib 10

← Back to all posts

© 2024 David Sargent Wood Disclaimer