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

[Maciej Piechotka]

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

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

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
place.

Regards

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

{-# RULES
    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