1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
-----------------------------------------------------------------------------
-- |
-- Module : Control.Monad.State.Lazy
-- Copyright : (c) Andy Gill 2001,
-- (c) Oregon Graduate Institute of Science and Technology, 2001
-- License : BSD-style (see the file LICENSE)
--
-- Maintainer : ross@soi.city.ac.uk
-- Stability : experimental
-- Portability : non-portable (type families)
--
-- Lazy state monads.
--
-- This module is inspired by the paper
-- /Functional Programming with Overloading and
-- Higher-Order Polymorphism/,
-- Mark P Jones (<http://web.cecs.pdx.edu/~mpj/>)
-- Advanced School of Functional Programming, 1995.
-----------------------------------------------------------------------------
module Control.Monad.State.Lazy (
-- * MonadState class
MonadState(..),
modify,
gets,
-- * The State monad
State,
runState,
evalState,
execState,
mapState,
withState,
-- * The StateT monad transformer
StateT(..),
evalStateT,
execStateT,
mapStateT,
withStateT,
module Control.Monad,
module Control.Monad.Fix,
module Control.Monad.Trans,
-- * Examples
-- $examples
) where
import Control.Monad.State.Class
import Control.Monad.Trans
import Control.Monad.Trans.State.Lazy
(State, runState, evalState, execState, mapState, withState,
StateT(..), evalStateT, execStateT, mapStateT, withStateT)
import Control.Monad
import Control.Monad.Fix
-- ---------------------------------------------------------------------------
-- $examples
-- A function to increment a counter. Taken from the paper
-- /Generalising Monads to Arrows/, John
-- Hughes (<http://www.math.chalmers.se/~rjmh/>), November 1998:
--
-- > tick :: State Int Int
-- > tick = do n <- get
-- > put (n+1)
-- > return n
--
-- Add one to the given number using the state monad:
--
-- > plusOne :: Int -> Int
-- > plusOne n = execState tick n
--
-- A contrived addition example. Works only with positive numbers:
--
-- > plus :: Int -> Int -> Int
-- > plus n x = execState (sequence $ replicate n tick) x
--
-- An example from /The Craft of Functional Programming/, Simon
-- Thompson (<http://www.cs.kent.ac.uk/people/staff/sjt/>),
-- Addison-Wesley 1999: \"Given an arbitrary tree, transform it to a
-- tree of integers in which the original elements are replaced by
-- natural numbers, starting from 0. The same element has to be
-- replaced by the same number at every occurrence, and when we meet
-- an as-yet-unvisited element we have to find a \'new\' number to match
-- it with:\"
--
-- > data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show, Eq)
-- > type Table a = [a]
--
-- > numberTree :: Eq a => Tree a -> State (Table a) (Tree Int)
-- > numberTree Nil = return Nil
-- > numberTree (Node x t1 t2)
-- > = do num <- numberNode x
-- > nt1 <- numberTree t1
-- > nt2 <- numberTree t2
-- > return (Node num nt1 nt2)
-- > where
-- > numberNode :: Eq a => a -> State (Table a) Int
-- > numberNode x
-- > = do table <- get
-- > (newTable, newPos) <- return (nNode x table)
-- > put newTable
-- > return newPos
-- > nNode:: (Eq a) => a -> Table a -> (Table a, Int)
-- > nNode x table
-- > = case (findIndexInList (== x) table) of
-- > Nothing -> (table ++ [x], length table)
-- > Just i -> (table, i)
-- > findIndexInList :: (a -> Bool) -> [a] -> Maybe Int
-- > findIndexInList = findIndexInListHelp 0
-- > findIndexInListHelp _ _ [] = Nothing
-- > findIndexInListHelp count f (h:t)
-- > = if (f h)
-- > then Just count
-- > else findIndexInListHelp (count+1) f t
--
-- numTree applies numberTree with an initial state:
--
-- > numTree :: (Eq a) => Tree a -> Tree Int
-- > numTree t = evalState (numberTree t) []
--
-- > testTree = Node "Zero" (Node "One" (Node "Two" Nil Nil) (Node "One" (Node "Zero" Nil Nil) Nil)) Nil
-- > numTree testTree => Node 0 (Node 1 (Node 2 Nil Nil) (Node 1 (Node 0 Nil Nil) Nil)) Nil
--
-- sumTree is a little helper function that does not use the State monad:
--
-- > sumTree :: (Num a) => Tree a -> a
-- > sumTree Nil = 0
-- > sumTree (Node e t1 t2) = e + (sumTree t1) + (sumTree t2)
|
