|
Chris@82
|
1 (*
|
|
Chris@82
|
2 * Copyright (c) 1997-1999 Massachusetts Institute of Technology
|
|
Chris@82
|
3 * Copyright (c) 2003, 2007-14 Matteo Frigo
|
|
Chris@82
|
4 * Copyright (c) 2003, 2007-14 Massachusetts Institute of Technology
|
|
Chris@82
|
5 *
|
|
Chris@82
|
6 * This program is free software; you can redistribute it and/or modify
|
|
Chris@82
|
7 * it under the terms of the GNU General Public License as published by
|
|
Chris@82
|
8 * the Free Software Foundation; either version 2 of the License, or
|
|
Chris@82
|
9 * (at your option) any later version.
|
|
Chris@82
|
10 *
|
|
Chris@82
|
11 * This program is distributed in the hope that it will be useful,
|
|
Chris@82
|
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Chris@82
|
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Chris@82
|
14 * GNU General Public License for more details.
|
|
Chris@82
|
15 *
|
|
Chris@82
|
16 * You should have received a copy of the GNU General Public License
|
|
Chris@82
|
17 * along with this program; if not, write to the Free Software
|
|
Chris@82
|
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
|
|
Chris@82
|
19 *
|
|
Chris@82
|
20 *)
|
|
Chris@82
|
21
|
|
Chris@82
|
22 (*************************************************************
|
|
Chris@82
|
23 * Monads
|
|
Chris@82
|
24 *************************************************************)
|
|
Chris@82
|
25
|
|
Chris@82
|
26 (*
|
|
Chris@82
|
27 * Phil Wadler has many well written papers about monads. See
|
|
Chris@82
|
28 * http://cm.bell-labs.com/cm/cs/who/wadler/
|
|
Chris@82
|
29 *)
|
|
Chris@82
|
30 (* vanilla state monad *)
|
|
Chris@82
|
31 module StateMonad = struct
|
|
Chris@82
|
32 let returnM x = fun s -> (x, s)
|
|
Chris@82
|
33
|
|
Chris@82
|
34 let (>>=) = fun m k ->
|
|
Chris@82
|
35 fun s ->
|
|
Chris@82
|
36 let (a', s') = m s
|
|
Chris@82
|
37 in let (a'', s'') = k a' s'
|
|
Chris@82
|
38 in (a'', s'')
|
|
Chris@82
|
39
|
|
Chris@82
|
40 let (>>) = fun m k ->
|
|
Chris@82
|
41 m >>= fun _ -> k
|
|
Chris@82
|
42
|
|
Chris@82
|
43 let rec mapM f = function
|
|
Chris@82
|
44 [] -> returnM []
|
|
Chris@82
|
45 | a :: b ->
|
|
Chris@82
|
46 f a >>= fun a' ->
|
|
Chris@82
|
47 mapM f b >>= fun b' ->
|
|
Chris@82
|
48 returnM (a' :: b')
|
|
Chris@82
|
49
|
|
Chris@82
|
50 let runM m x initial_state =
|
|
Chris@82
|
51 let (a, _) = m x initial_state
|
|
Chris@82
|
52 in a
|
|
Chris@82
|
53
|
|
Chris@82
|
54 let fetchState =
|
|
Chris@82
|
55 fun s -> s, s
|
|
Chris@82
|
56
|
|
Chris@82
|
57 let storeState newState =
|
|
Chris@82
|
58 fun _ -> (), newState
|
|
Chris@82
|
59 end
|
|
Chris@82
|
60
|
|
Chris@82
|
61 (* monad with built-in memoizing capabilities *)
|
|
Chris@82
|
62 module MemoMonad =
|
|
Chris@82
|
63 struct
|
|
Chris@82
|
64 open StateMonad
|
|
Chris@82
|
65
|
|
Chris@82
|
66 let memoizing lookupM insertM f k =
|
|
Chris@82
|
67 lookupM k >>= fun vMaybe ->
|
|
Chris@82
|
68 match vMaybe with
|
|
Chris@82
|
69 Some value -> returnM value
|
|
Chris@82
|
70 | None ->
|
|
Chris@82
|
71 f k >>= fun value ->
|
|
Chris@82
|
72 insertM k value >> returnM value
|
|
Chris@82
|
73
|
|
Chris@82
|
74 let runM initial_state m x = StateMonad.runM m x initial_state
|
|
Chris@82
|
75 end
|
