Do newtypes incur no cost even when you cannot pattern-match on them?

Question

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?

Answer 1

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.

Answer 2

It doesn't matter how deeply buried a newtype is in a stack of (fully) parametric types. At runtime, the values v :: Speed and w :: Double are completely indistinguishable – the wrapper is erased by the compiler, so even v is really just a pointer to a single 64-bit floating-point number in memory. Whether that pointer is stored in a list or tree or whatever doesn't make a difference either. getSpeed is a no-op and will not appear at runtime in any way at all.

So what do I mean by “fully parametric”? The thing is, newtypes can obviously make a difference at compile time, via the type system. In particular, they can guide instance resolution, so a newtype that invokes a different class method may certainly have worse (or, just as easily, better!) performance than the wrapped type. For example,

class Integral n => Fibonacci n where
  fib :: n -> Integer

instance Fibonacci Int where
  fib = (fibs !!)
   where fibs = [ if i<2 then 1
                         else fib (i-2) + fib (i-1)
                | i<-[0::Int ..] ]

this implementation is pretty slow, because it uses a lazy list (and performs lookups in it over and over again) for memoisation. On the other hand,

import qualified Data.Vector as Arr

-- | A number between 0 and 753
newtype SmallInt = SmallInt { getSmallInt :: Int }

instance Fibonacci SmallInt where
  fib = (fibs Arr.!) . getSmallInt
   where fibs = Arr.generate 754 $
           \i -> if i<2 then 1
                        else fib (SmallInt $ i-2) + fib (SmallInt $ i-1)

This fib is much faster, because thanks to the input being limited to a small range, it is feasible to strictly allocate all of the results and store them in a fast O (1) lookup array, not needing the spine-laziness.

This of course applies again regardless of what structure you store the numbers in. But the different performance only comes about because different method instantiations are called – at runtime this means simply, completely different functions.

Now, a fully parametric type constructor must be able to store values of any type. In particular, it cannot impose any class restrictions on the contained data, and hence also not call any class methods. Therefore this kind of performance difference can not happen if you're just dealing with generic [a] lists or Map Int a maps. It can, however, occur when you're dealing with GADTs. In this case, even the actual memory layout might be completely differet, for instance with

{-# LANGUAGE GADTs #-}

import qualified Data.Vector as Arr
import qualified Data.Vector.Unboxed as UArr

data Array a where
   BoxedArray :: Arr.Vector a -> Array a
   UnboxArray :: UArr.Unbox a => UArr.Vector a -> Array a

might allow you to store Double values more efficiently than Speed values, because the former can be stored in a cache-optimised unboxed array. This is only possible because the UnboxArray constructor is not fully parametric.