I would like Haskell better if it didn’t do its best to make me feel
stupid. Tasks that are *easy* in other languages, such, say, maintaining
some state or generating a random number, become difficult. After
banging my head on the State monad I finally arrived at a kind of
understanding, which I put here so I can restore context in the future!

Presume that you’ve got a function that, given a list, returns a list of booleans corresponding to whether the value was the first occurrence in the list. In Python it would look something like this:

```
def is_first(lst):
found = set()
r = []
for item in lst:
r.append(item not in found)
found.add(item)
return r
```

For example:

```
>>> is_first([1,2,3,1,4])
[True, True, True, False, True]
```

The most simplistic way of converting this to Haskell would require using recursion for the looping, resulting in the following (non-tail-recursive) function:

```
first lst = first' lst []
first' [] _ = []
first' (h:t) state =
if h `elem` found then False:(first' t state)
else True:(first' t (h:state))
```

The first’ function needs to “carry around” state as it loops around. Now, say that the lookup function is more complicated than we thought, so we break it out into a separate function. We have to pass around the state to all functions that access it, resulting in:

```
first lst = first' lst []
first' [] _ = []
first' (h:t) state =
if (isfound h state) then False:(first' t state)
else True:(first' t (h:state))
isfound h state = h `elem` state
```

Since isfound references the state, then it needs to be passed in explicitly.

I think that my main problem with understanding the State monad was that I kept wanting to treat the state as a global variable; so, I was thinking of “s <- get” and “put s” as references to a global stored somewhere, which left me with the question of “where is the initial put that sets the state?” Instead, though, you should think of “s <- get” and “put s” as references to an implicitly passed parameter.

The State Monad allows this particular pattern to be changed so that the state doesn’t need to be explicitly passed. Rewriting:

```
state_first lst = evalState (state_first' lst) []
state_first' [] = return []
state_first' (h:t) = do state <- get
let found = h `elem` state
put (if found then state else (h:state))
rest <- state_first' t
return $ (not found):rest
```

Basically, given a Haskell function, you can convert it into the state monad by:

- Removing the explicitly passed state
- Changing all references to the state parameter to “param <- get”
- Instead of recursively descending, use “put new-state-value”
- Calling a state returns using “<-” to ‘strip’ the value

Now, this doesn’t seem more elegant, but note that if you have to break functionality out, the state parameter no longer needs to be explicitly passed:

```
state_first lst = evalState (state_first' lst) []
state_first' [] = return []
state_first' (h:t) = do state <- get
found <- isfound h
put (if found then state else (h:state))
rest <- state_first' t
return $ (not found):rest
isfound h = do state <- get
return $ h `elem` state
```

UPDATED: following a question on #haskell (which was very friendly, especially to a complete newcomer), the following more elegant ways of solving this came up:

```
-- using mapAccum
first lst = snd $ mapAccumL first' [] lst
where first' acc x = (if found then acc else x:acc, not found)
where found = x `elem` acc
-- with mapM (not exactly equivalent to example)
first lst = evalState first' []
where first' = mapM (\a -> do state <- get; put (a:state); return $ not (a `elem` state)) lst
-- with mapM, equivalent to example
first lst = evalState first' []
where first' = mapM isfound lst
isfound a = do state <- get
let found = a `elem` state
put (if found then state else (a:state))
return $ not found
```

**For more information:**

Roll Your Own IRC
Bot

Grok Haskell Monad
Transformers

Monads For The Working Haskell
Programmer

Haskell Monads: Another
View

*Comments are moderated whenever I remember that I have a blog.*

Harry Xingzhi Pan | 2011-03-09 00:49:02

I believe in the third code block "found" should be "state".
Okay now I continue to read...

Reply
Alexandr | 2011-05-06 07:34:19

Good day! Thank you for the post, it is very helphul to understand State Monads.
But I think, example is very synthetic. Just look to this:
f :: [Integer] -> [Bool]
f xs = reverse $ f' $ reverse $ xs
where
f' [] = []
f' (x:xs) = [not (x `elem` xs)] ++ f' xs
It looks better, is not it?

Reply