State Monad for the Rest of Us (opens in new tab)

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)

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.

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?

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.

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)

monads in no way are a representation of state tho

Is there are correct way around?

    St -> (a, St)

vs

    St -> (St, a)

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

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