bundles/menhirLib/menhir-20120123/src/listMonad.ml

   1 (**************************************************************************)
   2 (*                                                                        *)
   3 (*  Menhir                                                                *)
   4 (*                                                                        *)
   5 (*  François Pottier, INRIA Rocquencourt                                  *)
   6 (*  Yann Régis-Gianas, PPS, Université Paris Diderot                      *)
   7 (*                                                                        *)
   8 (*  Copyright 2005-2008 Institut National de Recherche en Informatique    *)
   9 (*  et en Automatique. All rights reserved. This file is distributed      *)
  10 (*  under the terms of the Q Public License version 1.0, with the change  *)
  11 (*  described in file LICENSE.                                            *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 type 'a m = 'a list
  16
  17 let return x =
  18   [ x ]
  19
  20 let bind l f =
  21   List.flatten (List.map f l)
  22
  23 let ( >>= ) l f =
  24   bind l f
  25
  26 (*
  27    1. (return x) >>= f == f x
  28
  29    bind [ x ] f
  30    = List.flatten (List.map f [ x ])
  31    = f x
  32
  33    2. m >>= return == m
  34
  35    bind l return
  36    = List.flatten (List.map (fun x -> [ x ]) (x1::x2::..::xn))
  37    = List.flatten ([x1]::...::[xn])
  38    = x1::...::xn
  39    = l
  40
  41    3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)
  42
  43    bind (bind l f) g
  44    = List.flatten (List.map g (List.flatten (List.map f (x1::...::xn))))
  45    = List.flatten (List.map g (f x1 :: f x2 :: ... :: f xn))
  46    = List.flatten (List.map g ([fx1_1; fx1_2 ... ] :: [fx2_1; ... ] :: ...))
  47    = List.flatten ([ g fx1_1; g fx_1_2 ... ] :: [ g fx_2_1; ... ] ...)
  48    = List.flatten (List.map (fun x -> List.flatten (List.map g (f x))) l)
  49    = bind l (fun x -> bind (f x) g)
  50
  51 *)
  52