It shows how algorithms with mutable state can be implemented with pure functions, with immutable variables only.
The series itself is an excuse to take several detours on other Functional Programming topics: currying, partial application, recursion, Functors, Applicative Functors.
The source code includes F# and C# examples. In the next weeks it will be followed by code examples showing how to apply a state monad in practice.
On first glance, your example:
(decimal | DivideByZeroException) Divide(decimal n, decimal d) => n / d;
using System.Runtime.CompilerServices;
(decimal? , DivideByZeroException?) Divide(decimal n, decimal d) {
try {
return (n / d, null);
} catch {
return (null, new DivideByZeroException());
}
}
Divide(6, 2).Switch(
(result) => Console.WriteLine($"6 /2 is {result}"),
(ex) => Console.WriteLine("This is an exception!")
);
Divide(6, 0).Switch(
(result) => Console.WriteLine($"6 /2 is {result}"),
(ex) => Console.WriteLine("This is an exception!")
);
public class DivideByZeroException : Exception;
public static class TupleExtension {
public static void Switch<T, E>(this ValueTuple<T, E> tuple, Action<T> action1, Action<E> action2) {
if (tuple.Item1 is null && tuple.Item2 is null) {
} else if (tuple.Item1 is null) {
action2(tuple.Item2);
} else {
action1(tuple.Item1);
}
}
}
(null, null)
(result, new DivideByZeroException())
(btw, you're looking through the Monads For The Rest Of Us tutorial, but the the State Monad For The Rest Of Us tutorial is the one linked to this thread)
The second case, if there is an exception, it would be handled as such by simply switching the order of the `if` in the extension method. None of this seems confusing nor onerous in day-to-day use.
One minor thought: where you have `A Tree is either a Leaf or a Node containing 2 branches each containing another Tree structure.`, perhaps you could have `A Tree is either a Leaf or a Node _made of_ 2 branches each containing another Tree structure.`
So that "made of" easily maps to the "of" in F#'s type definition. Just an idea.
enum Tree {
Leaf,
Node(Box<Tree>, Box<Tree>),
}
fn number_of_leaves(tree: &Tree) -> u32 {
match tree {
Tree::Leaf => 1,
Tree::Node(left, right) => number_of_leaves(left) + number_of_leaves(right),
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn counts_the_number_of_leaves_in_a_tree() {
let tree_with_3_leaves = Tree::Node(
Box::new(Tree::Leaf),
Box::new(Tree::Node(
Box::new(Tree::Leaf),
Box::new(Tree::Leaf),
)),
);
let leaves = number_of_leaves(&tree_with_3_leaves);
assert_eq!(leaves, 3);
}
}Haskell will bring you more of the benefits from FP with expressive types; Idris will bring you even more. But you will lose the integration.
Same as F#, OCaml, etc.
I'm primarily a C# dev, but after dabbling in some F#, I concluded that most of the niceties in F# could also be done (to some extent and with some limitations) on C# as they have the same compile targets.
- representation of "the real world" where you can send data, control things, etc;
- representation of early return error semantics, like you have with exceptions;
- encapsulation of different execution threads, so you only interface with the group;
- encapsulation of a computer architecture, so something compiled for your GPU runs on the GPU, and something compiled for your CPU run on your CPU;
- encapsulation of transactions, so you can have a multi-threaded software changing whatever shared value you want and none of that leaks to the larger software;
- data structure, like libraries that encode hardware description into them.
That list is not in any way comprehensive. It's just stuff that I can remember right now.
For example, this is a really minimalistic arithmetic syntax tree interpreter in Haskell. You could write errors using the Either type:
data Term = Constant Int | Divide Term Term
eval :: Term -> Either String Int
eval (Constant n) = n
eval (Divide left right) =
case eval left of
Left errorString -> Left errorString
Right leftResult ->
case eval right of
Left errorString -> Left errorString
Right rightResult ->
if rightResult == 0
then Left "Division by zero"
else Right (div leftResult rightResult)
eval (Divide left right) = do
leftResult <- eval left
rightResult <- eval right
if rightResult == 0
then Left "Division by zero"
else Right (div leftResult rightResult)
The state monad is basically a wrapper over a pure function that takes a state and returns a tuple with the result and a new state. In an imperative language, you'd just actually change state, rather than doing that.
An example from this wiki page: https://en.wikibooks.org/wiki/Haskell/Understanding_monads/S...
In an imperative language, for pseudo-random numbers, you could modify global variables every time you want a new random number. Haskell lets you do this in IO functions. But a pure way would be to return the result of the new global variable every time.
-- randomR takes a range, so randomR (1,6) produces a random number between 1 and 6
rollPair :: StdGen -> ((Int, Int), StdGen)
rollPair s0 =
let (r1, s1) = randomR (1,6) s0
(r2, s2) = randomR (1,6) s1
in ((r1, r2), s2)
rollDieS :: State StdGen Int
rollDieS = state (randomR (1,6))
rollPairS :: State StdGen (Int, Int)
rollPairS = do
r1 <- rollDieS
r2 <- rollDieS
return (r1, r2) eval (Constant n) = Right n
eval (Constant n) = return nSo... it's a monad? I don't understand why this is worth calling State as distinct from non-State when that doesn't seem to add any meaning. Surely there must be something implied by a State monad that is not implied by a non-State monad. That seems relevant to call out in an introduction.
If I have an Int, then I just have an Int.
If I have an Identity Int, then I really still just have an Int.
If I have a [Int] then I have a list of Ints.
If I have a Maybe Int, then I either have an Int or I have Nothing.
If I have a Reader r Int, then I have a computation taking some input of type r and producing an Int. That computation can't modify the value of r.
If I have a State s Int, I have a computation taking some initial state of type s and producing an Int. The value of s may change during the computation.
All of these are monads, but calling all of them "state" is somewhat reductive.
The Haskell wiki tutorial on monads refers to them vaguely as "strategies" - I mostly agree with that description.
I tend to think of a monad in computer science as something which is constructed from a type and a computation and wraps the return values of that computation in that type. That allows you to bake in "context" into that type which could be state in the conventional sense but it could be something else.
To make this practical, let's make a simple example of a simple somewhat useful monad with no state. Imagine you have all the regular trigonometric functions sine, cosine etc which accept radians[1] and you need versions which work in degrees. You could make a unit conversion monad which converts arguments on the way in and wraps the result in an inverse conversion monad such that if you passed it to arcsine arccosine etc on it it would know and return degrees on the way out.
Neither of those monads would have any state in the usual computer science sense, the main conversion is just multiplying all the inputs by pi/180 before calling the wrapped function and constructing a result monad type so the inverse trig functions do the opposite of that.
[1] ie the correct versions. Fight me physicists and engineers and you freaks who use gradians whoever you are[2].
[2] I think it's surveyors but I could be wrong.
The point of monads, from the point of view of programmer convenience, is that they let you have a bag of contextual stuff along with your values. Thus if you think of a server application that processes requests, you might want to carry all of:
- configuration applicable to this request
(or global configuration)
- request metadata (time received, from where,
from whom, authenticated how, etc.)
- request processing state
- logs/traces
- I/O methods, so that
- you can make all your code deterministic
and thus easier to write tests for
- so you can mock the world (see previous
item)
Besides this there's everything about the Maybe ("Optional") and Error/Either monads that just makes it easy to make sure all errors and "nulls" are handled.
And what makes all of this possible (in Haskell) is the use of operators (functions) and syntax that lets one write "statements" that are actually combined into large expressions.
The key idea is that you can have something ressembling states with pure functions if you pass the a representation of the initial state as an argument and have the modified state be part of what the function return. You can then use this modified state as an argument for the next function call. The State monad is just an handy way to do this chaining.
But, yes, the actual state representation is in the way the argument is encoded, that's true.
Edit: I find it hilarious that I’m the one downvoted here while all the comments saying complete non sense about monads - including the ones clearly having no clue of what a monad actually is - are not. Never change HN.
A week or two ago, I found myself working in the same codebase. I had to do some refactoring and, thanks to the monad I had already established, the refactoring reduced code while expanding functionality. The best refactors happen when the patterns make it easy to do.
St -> (a, St)
get :: St -> (St, St)
put :: St -> (St -> ((), St))
{-# Language DerivingVia #-}
{-# Language GADTSyntax #-}
-- get :: My St
-- put :: St -> My ()
newtype My a where
My :: (St -> (a, St)) -> My a
deriving (Functor, Applicative, Monad, MonadState St, MonadFix)
via State St St -> (a, St)
St -> (St, a)
A monad is just a type constructor and two functions respecting some rules.
It can be widely different from the State monad ranging from useful (Option) to completely weird (the naive list monad) to doing nothing (identity monad).