haskellmonad-transformersstate-monad# State Monad - HASKELL

```
instance Monad ST where
--return :: a -> ST a
return x = S (\s -> (x,s))
--(>>=) :: ST a -> (a -> ST b) -> ST b
st >>= f = S (\s -> let (x, s') = app st s
in app (f x) s')
type State = Int
newtype ST a = S (State -> (a, State))
data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show)
app :: ST a -> State -> (a, State)
app (S st) s = st s
```

```
mlabel :: Tree a -> ST (Tree Int)
mlabel (Leaf _) = fresh >>= (\n -> return (Leaf n))
mlabel (Node l r) = mlabel l >>= (\l ->
mlabel r >>= (\r ->
return (Node l r)))
```

```
fresh :: ST Int
fresh = S (\n -> (n , n +1))
```

Hi, so this my code and I want to ensure that my understanding of the expansion of the mlabel function is correct. And I am not using any additional imports.

```
So suppose mlabel gets a input of Leaf 'a'
fresh >>== (\n -> return (Leaf n))
S (\n -> (n, n+1) >>== (\n -> return (Leaf n))
= S (\s -> let (x, s') = app (S (\n -> (n, n+1)) s
(x, s') = (s, s+1)
in app ((\n -> return (Leaf n) x) s'
= app (S (\x -> (Leaf x, x+1)) s'
= (\x -> (Leaf x, x+1) s'
= (Leaf s+1, (s+1)+1)
```

Solution

You haven't included the definitions of your `>>=`

and `return`

operations for this monad, but I assume you have something like:

```
return x = S (\s -> (x, s))
a >>= f = S $ \s ->
let (x, s') = app a s
in app (f x) s'
```

If so, there's a problem with your expansion here:

```
app ((\n -> return (Leaf n) x) s'
= app (S (\x -> (Leaf x, x+1)) s'
```

You've got a missing close parenthesis in the first line, and I think you skipped too many steps and got yourself turned around.

Anyway, this should look more like this:

```
app ((\n -> return (Leaf n)) x) s'
= app (return (Leaf x)) s' -- apply lambda
= app (S (\s -> (Leaf x, s))) s' -- definition of `return`
= (Leaf x, s') -- evaluate `app`
```

*Now*, when we substitute in the values of `x`

and `s'`

from `let (x, s') = (s, s+1) in ...`

, we get:

```
= (Leaf s, s+1)
```

and not `(Leaf s+1, (s+1)+1)`

.

It's probably safer to rewrite the whole `let xxx in yyy`

statement instead of trying to rewrite the `xxx`

and `yyy`

parts separately, so:

```
S $ \s -> let (x, s') = app (S (\n -> (n, n+1))) s
in app ((\n -> return (Leaf n)) x) s'
-- apply lambda
= S $ \s -> let (x, s') = app (S (\n -> (n, n+1))) s
in app (return (Leaf x)) s'
-- definition of `return`
= S $ \s -> let (x, s') = app (S (\n -> (n, n+1))) s
in app (S (\s -> (Leaf x, s))) s'
-- expand both `app` calls:
= S $ \s -> let (x, s') = (s, s+1)
in (Leaf x, s')
-- substitute `let` definitions:
= S $ \s -> (Leaf s, s+1)
```

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code