Thanks for your help.

...

Are there other ways to implement a counter in Haskell?

Using a State monad?

If I use your example on : test = let Node x l = enumeratedTree ( Node 'a' [undefined, Node 'b' []]) in tail l GHCI answers [Node (*** Exception: Prelude.undefined A monadic counter imposes an order of evaluation. In my program, I don't care about the order of the numbers. I only want them to be all different. I think a monad is too restrictive for what I need.

...

From some of my code:

let enumeratedTree = (`evalState` (0::Int)) $ (`mapTreeM` t) $ \x -> do n <- next return (n, x) next = do a <- get; put $! succ a; return a

where

mapTreeM :: Monad m => (a -> m b) -> Tree a -> m (Tree b) mapTreeM f (Node a ts) = do b <- f a ts' <- mapM (mapTreeM f) ts return (Node b ts')

(which could also be an instance of a popular non-standard FunctorM class)

Best regards Tomasz

On Wed, Mar 16, 2005 at 10:51:08AM +0100, Nicolas Oury wrote:

A monadic counter imposes an order of evaluation. In my program, I don't care about the order of the numbers. I only want them to be all different. I think a monad is too restrictive for what I need.

This is a common misconception, there is nothing about monads that requires an order of evaluation. for instance none of Control.Monad.Identity - isomorphic to not using monads at all Control.Monad.Reader - distributes a value to subcomputations Control.Monad.Writer - collects values from subcomputations imply any particular order of evaluation. This is one of the major powers of Monads, they can encapsulate all sorts of 'side effects', not just order of evaluation or linear state. for this app, I would use Control.Monad.State or if I needed the extra lazyness, Control.Monad.Reader with an explicitly splittable namesupply. John -- John Meacham - ⑆repetae.net⑆john⑈

Le 16 mars 05, à 11:08, Tomasz Zielonka a écrit :

On Wed, Mar 16, 2005 at 01:17:51AM +0100, Nicolas Oury wrote:

...

* linear implicit parameters

instance Splittable Int where split n = (2*n,2*n+1)

But I have a problem : the counter value increases exponentially. (I can only count up to 32 elements...)

Is there another way to split Int?

You could use unbounded Integers, or forget about numbers and use lists of bits.

newtype BitString = BitString [Bool]

instance Splittable BitString where split (BitString bs) = (BitString (False : bs), BitString (True : bs))

Best regards Tomasz

OK, I have written instance Splittable Integer where split n = (2*n,2*n+1) foo::(%x::Integer) => [a] -> [(a,Integer)] foo [] = [] foo (a:l) = (a,%x):(foo l) test = let %x = 1 in foo [1..15000] But, in this example, the numbering is linear and so test becomes quadratic. The main complexity of the program come from the numbering... (When you test it with ghci, this example is really slow) The same thing hapens with a list of bools. Best regards, Nicolas Oury

On Wed, 16 Mar 2005, Peter Davis wrote:

On 2005-03-16 02:52:39 -0800, Nicolas Oury said:

...

instance Splittable Integer where split n = (2*n,2*n+1)

I haven't played much with the Splittable class yet, but what would be wrong with

instance Splittable Integer where split n = (n,n+1)

If you recursively split the left-hand result then that overlaps with the right-hand result. Tony. -- f.a.n.finch http://dotat.at/ HUMBER THAMES DOVER: WEST OR SOUTHWEST 4 OR 5, OCCASIONALLY 6 IN HUMBER, BECOMING VARIABLE 3. OCCASIONAL RAIN OR DRIZZLE. MODERATE OR POOR WITH FOG BANKS.