Make it possible to evaluate monadic actions when assigning record fields

Isaac Dupree isaacdupree at
Sat Jul 14 19:04:26 EDT 2007

apfelmus wrote:
> I see, the dreaded name-supply problem. Well, it just seems that monads
> are not quite the right abstraction for that one, right? (Despite that
> monads make up a good implementation). In other words, my opinion is
> that it's not the monadic code that is over-linearized but the code that
> is over-monadized.
> The main property of a "monad" for name-supply is of course
>  f >> g  =  g >> f
> modulo alpha-conversion. Although we have to specify an order, it's
> completely immaterial. There _has_ to be a better abstraction than
> "monad" to capture this!

I agree completely!

It would be nice if the compiler could choose any order (or none at all, 
depending on implementation?) at its discretion.

If serialization(where the gaps are filled with actual strings as names) 
produces different results depending on the order (similar to 
name-supply *monad*: not(f >> g  =  g >> f) in a too-significant way), 
we have a purity violation if the order is not well-defined.  Big problem.

So we need to make sure they are used in an abstracted enough manner - 
perhaps only an instance of Eq, to make sharing/uniqueness/identity 
detectable, no more.  In dependently-typed languages I think we could 
have data structures that were fast but provably didn't depend in their 
operation on the material of ordering, for example, for lookup. 
Association-lists only need Eq but can be a little slow...  So with this 
technique in Haskell, Frisby for example would examine the infinite tree 
starting at the returned root, and choose an order for internal use 
based on the shape of the tree (which represents a *cyclic* graph) -- it 
would be unable to use ordering provided by name-supply 
sequencing(monad).  Which is just fine for it.  (except for being 
O((number of rules)^2) to construct a parser, using association lists, I 
think.)  Further abstraction could be added with a primitive 
UniqueNameMap of sorts, similar to (Map UniqueName a)... not enjoyable, 
so it might manage to be implemented in terms of some unsafe operations 
:-/. I hope my pessimism here is proved wrong :)


More information about the Haskell-prime mailing list