listMonad.ml 1.79 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13
(******************************************************************************)
(*                                                                            *)
(*                                   Menhir                                   *)
(*                                                                            *)
(*                       François Pottier, Inria Paris                        *)
(*              Yann Régis-Gianas, PPS, Université Paris Diderot              *)
(*                                                                            *)
(*  Copyright Inria. All rights reserved. This file is distributed under the  *)
(*  terms of the GNU General Public License version 2, as described in the    *)
(*  file LICENSE.                                                             *)
(*                                                                            *)
(******************************************************************************)

14 15
type 'a m = 'a list

16 17
let return x =
  [ x ]
18

19
let bind l f =
20 21
  List.flatten (List.map f l)

22
let ( >>= ) l f =
23 24
  bind l f

25
(*
26 27
   1. (return x) >>= f == f x

28 29 30
   bind [ x ] f
   = List.flatten (List.map f [ x ])
   = f x
31 32 33

   2. m >>= return == m

34
   bind l return
35
   = List.flatten (List.map (fun x -> [ x ]) (x1::x2::..::xn))
36
   = List.flatten ([x1]::...::[xn])
37 38 39 40
   = x1::...::xn
   = l

   3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)
41

42 43 44 45 46 47 48 49 50 51
   bind (bind l f) g
   = List.flatten (List.map g (List.flatten (List.map f (x1::...::xn))))
   = List.flatten (List.map g (f x1 :: f x2 :: ... :: f xn))
   = List.flatten (List.map g ([fx1_1; fx1_2 ... ] :: [fx2_1; ... ] :: ...))
   = List.flatten ([ g fx1_1; g fx_1_2 ... ] :: [ g fx_2_1; ... ] ...)
   = List.flatten (List.map (fun x -> List.flatten (List.map g (f x))) l)
   = bind l (fun x -> bind (f x) g)

*)