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

Maciej Piechotka uzytkownik2 at gmail.com
Tue Mar 9 09:36:51 EST 2010

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
(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).

The 'problem' is that if you combine O(f) algorithm and O(g) algorithm
resulting complexity is somewhere in between. For example head (O(1))
combined with sort (O(n log n)) gives us O(n) complexity.

Map have nice property that combined it 'borrows' complexity from
another algorithm. So g . map f have complexity of g (if f have O(1) of

I don't see any benefits of conv as:
- If the conversion is valid it is usually provided (see for example
mapMonotonic). Unfortunately Set is strict but I guess it belongs to
compiler optimization then conv function[1]
- If conversion is not valid it should not be performed in the first


[1] I don't know maybe something like:

    mapMonotonic/iso mapMonotonic <ISO> = unsafeCoerce

When <ISO> is special value which indicate newtype constructor (example
keyword). It is up to programmer (library or user - here user as it is
in preconditions) to assure that conversion is safe.

As in example given in other post Wrapped is not monotonic it cannot be
used argument as mapMonotonic (ok. due to precondition but still).
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20100309/df81b333/attachment.bin

More information about the Haskell-Cafe mailing list