From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id CAA02179; Thu, 13 Mar 2003 02:04:20 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id CAA05502 for ; Thu, 13 Mar 2003 02:04:18 +0100 (MET) Received: from wetware.wetware.com (wetware.wetware.com [199.108.16.1]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h2D13vf06722 for ; Thu, 13 Mar 2003 02:03:58 +0100 (MET) Received: from wetware.com([199.108.16.82]) (7635 bytes) by wetware.wetware.com via sendmail with P:esmtp/R:bind_hosts/T:inet_zone_bind_smtp (sender: ) id for ; Wed, 12 Mar 2003 16:54:19 -0800 (PST) (Smail-3.2.0.114 2001-Aug-6 #1 built 2002-Sep-2) Date: Wed, 12 Mar 2003 16:03:19 -0800 Reply-To: Ocaml Beginners Subject: [Caml-list] monads for dummies Content-Type: text/plain; charset=US-ASCII; format=flowed Mime-Version: 1.0 (Apple Message framework v551) Cc: Ocaml Beginners To: The Trade From: james woodyatt In-Reply-To: <3E6DDAFC.19000.44771B6@localhost> Message-Id: <3273E2D8-54E7-11D7-97B5-000393BA7EBA@wetware.com> Content-Transfer-Encoding: 7bit X-Mailer: Apple Mail (2.551) X-Spam: no; 0.00; woodyatt:01 jhw:01 wetware:01 monads:01 redirected:01 beginners:01 mgushee:01 havenrock:01 haskell:01 monad:01 immutable:01 monadic:01 composing:01 passing:01 higher-order:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk [followups redirected to ocaml_beginners@yahoogroups.com] On Tuesday, Mar 11, 2003, at 11:47 US/Pacific, mgushee@havenrock.com wrote: > > [...] My other big problem with Haskell was ... you guessed it: > monads! I > must have read every introduction to monads that's available on line > (and there are at least half a dozen), but I still don't really > understand them. [...] I'm a self-taught "programmer" with no formal education in mathematics or computer science, and I found the monad concept to be fairly difficult to learn. It took a leap of consciousness that feels about the same level of difficulty as what I remember needing to get through my high school calculus class. I've been seeing a lot of attempts to explain the theory lately, but most of them remind me of the kind of thing that I found more confusing than helpful when I was trying to get my head around the practical matters. What I really wanted is a Monads For Dummies tutorial. Here's what I remember being the crucial tip that got me over the hump: if you are working with immutable data structures (and there are at least three in the Ocaml standard library: Map, Set and List), then the monadic programming style can be really useful for composing complicated functions for manipulating the contents of those data structures from assemblies of simpler functions. Without the monadic programming style, you end up concocting huge specialized functions for passing into the higher-order standard library functions, e.g. fold, map, filter, etc., and achieving any kind of modularity requires careful design work. The problem can quickly become hard enough that learning monadic programming starts to seem like a decent trade. Once you start using immutable data structures in complex ways (e.g. doing lots of weird transformations on 'a list values), you may find that writing your functions as monads will help you modularize your program, allowing you to encapsulate and reuse computations that would otherwise be duplicated in scattered fragments of code all over the place. (Alternatively, you may want to use mutable data structures instead, which is always a popular way out of this problem.) If you discover your immutable data structure manipulations are getting out of hand, and you want to reorganize your code for better encapsulation and reusability-- without changing them to use mutable data structures instead-- then I recommend learning about the continuation monad first. Here is the signature of a module I use for the continuation monad in Ocaml: type ('x, 'a) t = ('a -> 'x) -> 'x (* let ( >>= ) m f x = m (fun a -> f a x) *) val ( >>= ): ('x, 'a) t -> ('a -> ('x, 'b) t) -> ('x, 'b) t val return: 'a -> ('x, 'a) t (* let return x f = f x *) val lift: 'x -> ('x, 'a) t (* let lift x _ = x *) val cont: ('x -> 'x) -> ('x, unit) t (* let cont f g = f (g ()) *) val eval: ('x, unit) t -> 'x -> 'x (* let eval m x = m (fun () -> x) *) By using this module, I can make new continuations (functions of type 'x -> 'x) by composing appropriate instances of the continuation monad type and binding them with functions that chain the results of previous computations into the subsequent computations. For a very simple example: if you have a bunch of continuation functions, e.g. f1, f2, f3 each of type 'x -> 'x, then you can compose them in sequence like so: let m: ('x, unit) t = cont f1 >>= fun _ -> cont f2 >>= fun _ -> cont f3 In fact, it might be easier to represent f1, f2 and f3 as their monads to begin with: let m1: ('x, unit) t = cont f1 let m2: ('x, unit) t = cont f2 let m2: ('x, unit) t = cont f3 let m: ('x, unit) t = m1 >>= fun _ -> m2 >>= fun _ -> m3 This defines a new instance of the continuation monad type, but it isn't exactly the composed continuation function yet. You *evaluate* the monad to get the continuation it represents: let f: 'x -> 'x = eval m The 'return' function is also sometimes called the 'unit' function (but 'unit' is a reserved word in Ocaml, so I like to avoid it). It constructs a monad that passes a value through the ( >>= ) operator to the function that constructs a new monad value with it. It's good for use in monad functions that take input from "outside" the encapsulation and pass it along to other monads. The 'lift' function is a variant of the 'cont' function which ignores the 'x value that is input from any previous computation and produces the 'lifted' value as output. It's good for use in monad functions that initialize (or reinitialize) the encapsulated value of the monad. I probably should have named it 'init' instead. If I were writing a book on using monads for dummies, I'd launch here into a series of useful examples showing how to use monads to simplify very complicated list manipulation functions. The example above is too simple to show the power of monadic programming adequately. I don't have the time, but it's certainly something that needs to be done. The continuation monad is only the beginning. There are several fundamental types of monad, and it's possible to combine them into composites to support more operations, e.g. state manipulation, exception handling, backtracking, etc. Once you understand how to use monads in a systematic design, you can take better advantage of the support for pure functional programming available in the Ocaml language. In lieu of my writing a long list of examples, here is a paper that I found immensely helpful in the learning process: The examples are written in Haskell, but I found them pretty easy to translate in my head to the equivalent Ocaml. Warning: you don't have to go down this path very far before you will begin to chafe at the "operator overloading" problem. You can't define a ( >>= ) operator that will be good for all monad types. I don't know how to explain exactly why. You just can't. Some folks have proposed that "extensional polymorphism" would be very helpful in helping solve the problem. I buy that. Warning2: since Ocaml strictly evaluates all the arguments to a function before executing it (unless the argument is of type 'a Lazy.t), you really can't define a proper ( >> ) operator for your monads. It won't work the same as the one in Haskell, because Ocaml evaluates the right operand before it's needed, and you don't buy anything by fixing it so that it takes a Lazy.t value instead. If what I've written isn't very helpful to you, then please tell me so I know not to try to explain this stuff to people. On the other hand, if it *is* helpful, that would be nice to know too. -- j h woodyatt that's my village calling... no doubt, they want their idiot back. ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners