Re: [Haskell-cafe] Re: generalized newtype deriving allows the definition of otherwise undefinable functions
On Tuesday 09 March 2010 9:36:51 am Maciej Piechotka wrote: On Mon, 2010-03-08 at 23:32 +0100, Wolfgang Jeltsch wrote: For example, with the above conv method, you could probably convert a list of some type [t] into a list of type [Wrapped t] in O(1) time. If you would code this conversion by hand, it would take O(n) time, of course. Wouldn't timing be exactly the same? I mean: (map Wrapped xs) !! k and (conv xs :: [Wrapped t]) !! k They have exactly the same 'complexity' - O(k) (if k is constant we have constant time access - even if list is infinite). Comparing the complexity isn't really going to tell you which of these does more work. If n is O(m), then an algorithm that takes 'm + n' steps has the same overall complexity as one that simply takes 'm' steps, but obviously the first does more work. 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. -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: generalized newtype deriving allows the definition of otherwise undefinable functions
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/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: generalized newtype deriving allows the definition of otherwise undefinable functions
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? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
