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 -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/