[Haskell-cafe] ANN: combinatorics

[Jean-Marie Gaillourdet]

Hi, 
On 29.01.2012, at 23:30, wren ng thornton wrote:

> On 1/29/12 5:48 AM, Roman Cheplyaka wrote:
>> * wren ng thornton<wren at freegeek.org>  [2012-01-28 23:06:08-0500]
>> 
>> Why not to make it more pure? That is, return a lazy list of Ints (but
>> not a CAF), which user can throw away by the usual GC means?
>> 
>> The functions from the other modules that use primes would have to be
>> put in a Reader monad. That would make it a little bit more awkward to
>> use, but personally I'd prefer that over memory leaks.
> 
> I'd also prefer a more pure solution, but I don't think that the Reader monad is the right tool here. I played around with that approach, but it requires extremely invasive changes to client code, obfuscating what should be simple mathematical formulae. And, it's too fragile, exposing the implementation in a way that breaks client code should I change a non-prime-using algorithm to a prime-using one, or vice versa. The fragility could be partially avoided by providing both prime-using and non-prime-using algorithms, but then that forces users to decide which one they want--- and if their only concern is performance, then they'd have to go through the code-breaking refactoring anyways, just to determine which is faster for their application.
> 
> One alternative I'm exploring is, rather than (only) making the primes not a CAF, instead make the prime-using functions non-CAFs as well. That is, provide a makePrimeUsingFunctions function which returns a record/tuple of all the functions, sharing a stream of primes. This way, after allocating the functions, they can be used purely just as in the current model; and when the client wants the primes to be GCed, they can drop their references to the allocated functions which use those primes (allocating new functions later, if necessary).

A slight variation on that approach is to use implicit parameters to parameterize your functions by the primes. Something allong the following lines:

> {-# LANGUAGE ImplicitParams, Rank2Types #-}
>  
>  
> data PrimeTable                 -- abstract
>  
> withPrimes :: ((?primes :: PrimeTable) => a) -> a
> withPrimes e = e
>   where
>     ?primes = ...
>  
>  
> factorial :: (?primes :: PrimeTable) => Integer -> Integer
> factorial = ...
>  
> example = withPrimes $ ... factorial n ….

This has the advantage that the user doesn't have to bring all the elemnts of your tuple/record into scope. 
And you can have two modules with an almost identical content, one uses the implicit primes argument and the other uses a global CAF for its primes. A user would only have to change his type signatures and strategically add/remove a call to withPrimes when switching.  

Cheers,
  Jean