5 ms·

State Monad for the Rest of Us

arialdomartini 2y ago
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.
- CharlieDigital 2y 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)
  - itishappy 2y 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)
    - CharlieDigital 2y ago
      I don't see those as necessarily illegal states, but even so, it's not hard to handle by adding a third `Action` for it (I kept the example short and left the first `if` condition empty). 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.
      - itishappy 2y ago
        What does it mean to receive both value and error in the context of division? What about neither? The issue is not that they cannot be handled, it's that they can be. You included an entire extra branch and check for something that will never occur because they're legal values for your tuple type. I assume it'll be optimized out of this trivial example, but imagine writing a function to receive your tuple type in a codebase where you didn't create the tuple. ADTs prevent this entire worry because there is no way to represent illegal states.
        CharlieDigital 2y ago
        What does it mean to receive both value and error in the context of division? What about neither? It's only "invalid" if you define it as such. We can state "if we receive neither, then this is the same as an error state". And "if we receive both, than an exception occurred and should be handled". I don't see the issue?
- airstrike 2y 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.
  - itishappy 2y ago
    Given that the book opens by defining a recursive datatype, it would be an exercise in frustration to port this to Rust...
    - airstrike 2y ago
      How so? Can't you just put your Tree in a Box? 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); } }
      - itishappy 2y ago
        Geez, that's way easier than I remembered. When I originally encountered this while learning Rust I figured recursion was my problem and switched to learning Haskell. (No regrets.) I guess I need to take my findings back to Rust!
      - marcosdumay 2y ago
        Yes, and the frustration is on dealing with all the boxes and unboxing, at the exact correct place, and that won't unify with each other. There's a sibling comment about porting it to C#. The Rust version will be less frustrating than the C#, but it is the same kind of bad. On Rust specifically, this happens because Rust is a low level language.
- behnamoh 2y 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?
  - CharlieDigital 2y 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 2y 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.
  - solomonb 2y 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.
    - lupire 2y ago
      Impure functions lack referential transparency, which is often sacrificed but kind of important to being a function - getting the same result every time you call it with the same input. Alternatively, you can say that every function has an implicit input parameter of the the current program state, but that turns every function on one bit of input to a potentially astronomically complex function of gigabytes of input.
      - solomonb 2y ago
- justincredible 2y ago
  [dead]
deleted 2y ago
[deleted]
darby_nine 2y 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 2y ago
  monads in no way are a representation of state tho
  - darby_nine 2y 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?
    - Izkata 2y ago
      They are an abstraction of a sequence of operations, not the state used in those operations.
      - darby_nine 2y ago
        They're both, right? It's not like it specifically ignores the inputs and outputs of those operations. These are specifically entailed in the definition of the monad. I strongly, strongly suspect there's something about how F# processes monads in the context of a do expression that explains what is the focus here. Unfortunately I don't have the time to go through the steps now, hence why I specifically recommended modifying the introduction to give some clue about the terms involved.
        Izkata 2y ago
        An "if" statement or "map" function also has inputs and outputs and probably some internal state due to implementation details, but we don't say they represent state either. They represent operations, or a sequence of operations.
Iceland_jack 2y 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 2y ago
  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!
  - chuckadams 2y 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.
  - RandomThoughts3 2y 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 2y 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_monads/ 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_ 2y ago
Isn't every monad a state monad?
- RandomThoughts3 2y 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).

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.

CharlieDigital 2y 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)
- itishappy 2y 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)
  - CharlieDigital 2y ago
    I don't see those as necessarily illegal states, but even so, it's not hard to handle by adding a third `Action` for it (I kept the example short and left the first `if` condition empty). 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.
    - itishappy 2y ago
      What does it mean to receive both value and error in the context of division? What about neither? The issue is not that they cannot be handled, it's that they can be. You included an entire extra branch and check for something that will never occur because they're legal values for your tuple type. I assume it'll be optimized out of this trivial example, but imagine writing a function to receive your tuple type in a codebase where you didn't create the tuple. ADTs prevent this entire worry because there is no way to represent illegal states.
      - CharlieDigital 2y ago
        What does it mean to receive both value and error in the context of division? What about neither? It's only "invalid" if you define it as such. We can state "if we receive neither, then this is the same as an error state". And "if we receive both, than an exception occurred and should be handled". I don't see the issue?
airstrike 2y 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.
- itishappy 2y ago
  Given that the book opens by defining a recursive datatype, it would be an exercise in frustration to port this to Rust...
  - airstrike 2y ago
    How so? Can't you just put your Tree in a Box? 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); } }
    - itishappy 2y ago
      Geez, that's way easier than I remembered. When I originally encountered this while learning Rust I figured recursion was my problem and switched to learning Haskell. (No regrets.) I guess I need to take my findings back to Rust!
    - marcosdumay 2y ago
      Yes, and the frustration is on dealing with all the boxes and unboxing, at the exact correct place, and that won't unify with each other. There's a sibling comment about porting it to C#. The Rust version will be less frustrating than the C#, but it is the same kind of bad. On Rust specifically, this happens because Rust is a low level language.
behnamoh 2y 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?
- CharlieDigital 2y 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 2y 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.
- solomonb 2y 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.
  - lupire 2y ago
    Impure functions lack referential transparency, which is often sacrificed but kind of important to being a function - getting the same result every time you call it with the same input. Alternatively, you can say that every function has an implicit input parameter of the the current program state, but that turns every function on one bit of input to a potentially astronomically complex function of gigabytes of input.
    - solomonb 2y ago
justincredible 2y ago
[dead]

deleted 2y ago

[deleted]

darby_nine 2y 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 2y ago
monads in no way are a representation of state tho
- darby_nine 2y 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?
  - Izkata 2y ago
    They are an abstraction of a sequence of operations, not the state used in those operations.
    - darby_nine 2y ago
      They're both, right? It's not like it specifically ignores the inputs and outputs of those operations. These are specifically entailed in the definition of the monad. I strongly, strongly suspect there's something about how F# processes monads in the context of a do expression that explains what is the focus here. Unfortunately I don't have the time to go through the steps now, hence why I specifically recommended modifying the introduction to give some clue about the terms involved.
      - Izkata 2y ago
        An "if" statement or "map" function also has inputs and outputs and probably some internal state due to implementation details, but we don't say they represent state either. They represent operations, or a sequence of operations.

Iceland_jack 2y 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 2y ago
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!
- chuckadams 2y 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.
- RandomThoughts3 2y 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 2y 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_monads/ 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_ 2y ago

Isn't every monad a state monad?

RandomThoughts3 2y 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).