How can I make a counter without Monad?

[Nicolas Oury]

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