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

Dan Doel dan.doel at gmail.com
Tue Mar 9 14:16:11 EST 2010

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