From posting-system@google.com Wed Oct 10 01:42:11 2001 Date: Tue, 9 Oct 2001 22:42:03 -0700 Reply-To: oleg@pobox.com From: oleg@pobox.com (oleg@pobox.com) Newsgroups: comp.lang.functional Subject: Re: How to do this functionally? References: Message-ID: <7eb8ac3e.0110092142.3fef83e3@posting.google.com> X-Comment: added more comments Status: OR dr_pibb@hotmail.com (Dr Pibb) wrote in message news:... > An obvious way to implement it in this way is to have a collection of > state which is passed along all the time to every function. But this > seems rather tedious. I could also use the ST "lazy state thread" > module, which would perhaps elminate some of the tedium... You can build your own monad -- that will effectively hide the counter (which you use to tag every node) Here's an example --First, some framework type Numbered a = (Int,a) newtype NumberedM a = NumberedM (Int -> Numbered a) instance Monad NumberedM where NumberedM m >>= f = NumberedM $ \n -> let (n1,v) = (m n) NumberedM m' = f v (n1',v') = (m' n1) in (n1',v') return x = NumberedM $ \n -> (n,x) -- additional monad morphisms -- get the current id and increment it incr:: NumberedM Int incr = NumberedM $ \n -> (n+1,n) run_numberedM:: NumberedM a -> Int -> Numbered a run_numberedM (NumberedM m) init_count = m init_count -- Now, on to applications: trees -- The basic tree datatype data Tree a = Nd a (Forest a) deriving Show type Forest a = [Tree a] -- Here's a function that creates a new node and tags its value -- with a unique number make_node val kids = do { n <- incr; return (Nd (n,val) kids) } -- Finally, let's try to build a binary tree make_btree:: Int -> NumberedM (Tree (Numbered Int)) -- Note the algorithm does not explicitly mention any counter -- at all: it looks like a regular algorithm for building a binary tree. -- There is an important difference: the left branch is constructed -- strictly _before_ the right branch. The parent node of two branches -- is constructed strictly after. The Algorithm is _serialized_: the -- consequence of using the monad. make_btree 0 = make_node 0 [] make_btree depth = do { left <- make_btree (depth -1); right <- make_btree (depth -1); make_node depth [left, right] } -- Let's see what we've got Main> run_numberedM (make_btree 1) 100 (103,Nd (102,1) [Nd (100,0) [], Nd (101,0) []]) The result is a pair (the_resulting_count,tree) We tag each node with a unique counter, an integer that starts at 100 and counts forward. Main> run_numberedM (make_btree 3) 100 (115,Nd (114,3) [Nd (106,2) [Nd (102,1) [Nd (100,0) [], Nd (101,0) []], Nd (105,1) [Nd (103,0) [], Nd (104,0) []]], Nd (113,2) [Nd (109,1) [Nd (107,0) [], Nd (108,0) []], Nd (112,1) [Nd (110,0) [], Nd (111,0) []]]]) It does seem to work, don't you think?