[Haskell-cafe] Re: generalized newtype deriving allows the
definition of otherwise undefinable functions
john at repetae.net
Tue Mar 9 14:24:27 EST 2010
On Tue, Mar 09, 2010 at 02:16:11PM -0500, Dan Doel wrote:
> 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).
> So, if 'id xs !! k' takes costs f(k), then 'map id xs !! k' costs f(k) + C*k.
> Both are O(k), but the latter is more expensive.
Not to mention they can have radically different space usages.
xs = 'x':xs
id xs => constant space
map id xs => potentially infinite space
John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/
More information about the Haskell-Cafe