State Monad for the Rest of Us

https://arialdomartini.github.io/state-monad-for-the-rest-of-us

47 57 2 years ago

arialdomartini.github.io

A series of articles starting from the very scratch and getting to the State Monad. It's thought to be novice-friendly: although using F#, it assumes no knowledge of it. If only it aroused someone's curiosity around F#, that would make my day.

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.

CharlieDigital4• 2 years ago

Not all the ways through it, but a good intro.

On first glance, your example:

    (decimal | DivideByZeroException) Divide(decimal n, decimal d) => n / d;

Isn't that far off from what is pretty easily done in C#:

    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);
        }
      }
    }

(Sharing for folks who aren't familiar with C# Tuple types and extension methods)

itishappy5• 2 years ago

You'll be keeping a lot more info in your head with your approach. For instance, the following illegal states have legal representations in your system:

    (null, null)
    (result, new DivideByZeroException())

Hence your unhandled base case in the extension method. Sum types are a more accurate representation and more pleasant to use as a result.

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

jyufnlwfnzvbm2• 2 years ago

You'd love Go because they also treat Sums as Ad-Hoc Product types.

airstrike3• 2 years ago

Very cool, thanks for sharing. I wonder how easy it would be to port this to Rust, just for the heck of it...

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.

itishappy5• 2 years ago

Given that the book opens by defining a recursive datatype, it would be an exercise in frustration to port this to Rust...

arialdomartini2• 2 years ago

Cool idea! Thank you for the suggestion. Fixed!

behnamoh• 2 years ago

For someone who's curious about these topics, do you recommend F# as a language to learn and apply them in practice? I've always thought of Haskell as THE functional programming language because of its purity and elegant syntax which looks very much like math. But lately I've seen people talk about F#, Clojure, ... and I wonder if Haskell is mostly an academic language whereas these are mostly practical?

CharlieDigital4• 2 years ago

F# is not particularly practical as far as jobs go, but it benefits from the large C# ecosystem.

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.

agentultra• 2 years ago

Haskell is far from being an academic language. It’s used in industry and has very practical features and libraries.

Same as F#, OCaml, etc.

solomonb2• 2 years ago

A lot of people mistake Purity as a language feature for meaning a more pure functional language. What makes a language functional is that their basic unit of abstraction is functions, not whether they isolate IO effects by default.

Iceland_jack2• 2 years ago

Haskell focuses on both, but prioritizes research. I have had several Haskell jobs and highly recommend it for the personal enjoyment.

marcosdumay3• 2 years ago

Those two languages are popular because they bring some of the benefit of languages like Haskell into an environment that is compatible with an outdated but widely used OOP language.

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.

darby_nine6• 2 years ago

You should probably mention in the introduction what the state monad is to those who don't use F#. At first blush it just seems redundant—what is a monad if not a representation of state?

whateveracct• 2 years ago

monads in no way are a representation of state tho

darby_nine6• 2 years ago

How do you figure? They're an abstract concept commonly used to represent values over a sequence of operations. How does that not describe state? Do you mean something very specific with the term "state" that might make it more meaningful?

RandomThoughts34• 2 years ago

It's not about monads as an abstract concept. It's specifically about the State monad.

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.

trealira5• 2 years ago

You can also use it for representing errors, for representing global read-only variables, for representing global write-only variables, for representing non-determinism, for representing continuations, and other things (since you can write your own).

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)

It's cumbersome, and there's a staircase growing. Because Either is a monad, you could rewrite the division op like this:

  eval (Divide left right) = do
    leftResult <- eval left
    rightResult <- eval right
    if rightResult == 0
      then Left "Division by zero"
      else Right (div leftResult rightResult)

This is a good article about the either monad: https://mmhaskell.com/blog/2022/3/3/using-either-as-a-monad

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)

It's annoying. You could use the state monad to simplify this:

  rollDieS :: State StdGen Int
  rollDieS = state (randomR (1,6))

  rollPairS :: State StdGen (Int, Int)
  rollPairS = do
    r1 <- rollDieS
    r2 <- rollDieS
    return (r1, r2)

darby_nine6• 2 years ago

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.

So... 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.

trealira5• 2 years ago

Just realized I should have written one of these for the Constant evaluation:

  eval (Constant n) = Right n
  eval (Constant n) = return n

marcosdumay3• 2 years ago

Some uses you'll find in Haskell:

- 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.

Iceland_jack2• 2 years ago

Any function matching the type

    St -> (a, St)

can viewed as `State St' parameterized over `a'. There are several behaviors that organize such functions, such as Monad which "overloads the semicolon" to work on stateful computations. Another behavior implements a stateful interface: `MonadState St'.

    get :: St -> (St, St)
    put :: St -> (St -> ((), St))

With type classes in Haskell, behaviour is type-directed so in order to reap the benefits we declare a new type.

    {-# 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

greener_grass• 2 years ago

Is there are correct way around?

    St -> (a, St)

    St -> (St, a)

I've found both in the wild and it can be very confusing!

chuckadams• 2 years ago

The order doesn’t matter as long as you’re consistent, but Control.Monad.State uses the first, and you’ll have a bad time (in Haskell anyway) if you’re not compatible with that.

RandomThoughts34• 2 years ago

It’s the same thing. Order doesn’t matter in the tuple. Just use a bind which is in line with the signature of the type you want to use.

ashton314• 2 years ago

Monad patterns cut down on boilerplate even in languages where you might not strictly “need” them. I’ve been working on a project in Elixir and I found the writer monad to be exactly what I needed. I wrote about it here: https://lambdaland.org/posts/2024-05-01_definitely_not_about...

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.

loa_in_• 2 years ago

Isn't every monad a state monad?

RandomThoughts34• 2 years ago

Not at all.

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).

State Monad for the Rest of Us

Related Stories