[Haskell-cafe] Re: generalized newtype deriving allows the definition of otherwise undefinable functions

Evan Laforge qdunkan at gmail.com
Tue Mar 9 14:46:09 EST 2010

> The difference (in work) between map Wrapped and conv is the difference
> between map id and id :: [a] -> [a]. In the absence of any fusion/rewrite
> rules, the former breaks down a list, and builds up a new one with exactly the
> same elements (or, every element x becomes an id x thunk, perhaps). So, in a
> lazy language, inspecting each cons cell carries an additional O(1) overhead
> over inspecting the corresponding cons cell in the original list (because
> inspecting the former implicitly inspects the latter, and then yields a new
> cons cell with the same values for inspection).

On a related note, I've been occasionally worried about conversions
like 'map convert huge' where 'convert' is from one newtype to another
with the same underlying type.  I tried some simple examples and
looking at core it seems like the 'map id huge' is optimized away.

However, I'm guessing that's only because of a 'map id xs -> id xs'
rewrite rule involved, and it won't work for all data structures.  It
seems like a better solution than relying on rewrite rules would be to
lift the newtype up one level, e.g. convert 'M (Newtype x)' to
'Newtype (M x)'.  Actually what I really want is to replace every
function that goes M x -> x with M x -> Newtype x, but we don't have
parameterized modules and doing this for something like Data.Map means
a lot of boilerplate.

Surely there is some more general approach?

More information about the Haskell-Cafe mailing list