Context

Most Haskell tutorials I know (e.g. LYAH) introduce newtypes as a cost-free idiom that allows enforcing more type safety. For instance, this code will type-check:

type Speed = Double
type Length = Double

computeTime :: Speed -> Length -> Double
computeTime v l = l / v

but this won't:

newtype Speed = Speed { getSpeed :: Double }
newtype Length = Length { getLength :: Double }

-- wrong!
computeTime :: Speed -> Length -> Double
computeTime v l = l / v

and this will:

-- right
computeTime :: Speed -> Length -> Double
computeTime (Speed v) (Length l) = l / v

In this particular example, the compiler knows that Speed is just a Double, so the pattern-matching is moot and will not generate any executable code.

Question

Are newtypes still cost-free when they appear as arguments of parametric types? For instance, consider a list of newtypes:

computeTimes :: [Speed] -> Length -> [Double]
computeTimes vs l = map (\v -> getSpeed v / l) vs

I could also pattern-match on speed in the lambda:

computeTimes' :: [Speed] -> Length -> [Double]
computeTimes' vs l = map (\(Speed v) -> v / l) vs

In either case, for some reason, I feel that real work is getting done! I start to feel even more uncomfortable when the newtype is buried within a deep tree of nested parametric datatypes, e.g. Map Speed [Set Speed]; in this situation, it may be difficult or impossible to pattern-match on the newtype, and one would have to resort to accessors like getSpeed.

TL;DR

Will the use of a newtype never ever incur a cost, even when the newtype appears as a (possibly deeply-buried) argument of another parametric type?

On their own, newtypes are cost-free. Applying their constructor, or pattern matching on them has zero cost.

When used as parameter for other types e.g. [T] the representation of [T] is precisely the same as the one for [T'] if T is a newtype for T'. So, there's no loss in performance.

However, there are two main caveats I can see.

newtypes and instances

First, newtype is frequently used to introduce new instances of type classes. Clearly, when these are user-defined, there's no guarantee that they have the same cost as the original instances. E.g., when using

newtype Op a = Op a
instance Ord a => Ord (Op a) where
    compare (Op x) (Op y) = compare y x

comparing two Op Int will cost slightly more than comparing Int, since the arguments need to be swapped. (I am neglecting optimizations here, which might make this cost free when they trigger.)

newtypes used as type arguments

The second point is more subtle. Consider the following two implementations of the identity [Int] -> [Int]

id1, id2 :: [Int] -> [Int]
id1 xs = xs
id2 xs = map (\x->x) xs

The first one has constant cost. The second has a linear cost (assuming no optimization triggers). A smart programmer should prefer the first implementation, which is also simpler to write.

Suppose now we introduce newtypes on the argument type, only:

id1, id2 :: [Op Int] -> [Int]
id1 xs = xs                    -- error!
id2 xs = map (\(Op x)->x) xs

We can no longer use the constant cost implementation because of a type error. The linear cost implementation still works, and is the only option.

Now, this is quite bad. The input representation for [Op Int] is exactly, bit by bit, the same for [Int]. Yet, the type system forbids us to perform the identity in an efficient way!

To overcome this issue, safe coercions where introduced in Haskell.

id3 :: [Op Int] -> [Int]
id3 = coerce

The magic coerce function, under certain hypotheses, removes or inserts newtypes as needed to make type match, even inside other types, as for [Op Int] above. Further, it is a zero-cost function.

Note that coerce works only under certain conditions (the compiler checks for them). One of these is that the newtype constructor must be visible: if a module does not export Op :: a -> Op a you can not coerce Op Int to Int or vice versa. Indeed, if a module exports the type but not the constructor, it would be wrong to make the constructor accessible anyway through coerce. This makes the "smart constructors" idiom still safe: modules can still enforce complex invariants through opaque types.