Не несут ли новые типы никаких затрат, даже если вы не можете сопоставить их по образцу?

контекст

Большинство учебных пособий по Haskell, которые я знаю (например, LYAH), представляют новые типы как бесплатную идиому, которая позволяет обеспечить большую безопасность типов. Например, этот код будет проверять тип:

type Speed = Double
type Length = Double

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

но это не будет

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

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

и это будет:

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

В этом конкретном примере компилятор знает, что Speed это просто Double, так что сопоставление с образцом является спорным и не будет генерировать никакого исполняемого кода.

Вопрос

Являются ли новые типы все еще бесплатными, когда они появляются в качестве аргументов параметрических типов? Например, рассмотрим список новых типов:

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

Я также могу сопоставить паттерн по скорости в лямбде:

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

В любом случае, по какой-то причине, я чувствую, что настоящая работа делается! Я начинаю чувствовать себя еще более неловко, когда новый тип похоронен в глубоком дереве вложенных параметрических типов данных, например Map Speed [Set Speed]; в этой ситуации может быть трудно или невозможно сопоставить шаблон с новым типом, и придется прибегнуть к таким средствам доступа, как getSpeed,

TL;DR

Разве использование нового типа никогда не будет сопряжено с какими- либо издержками, даже если новый тип выглядит как (возможно, глубоко скрытый) аргумент другого параметрического типа?

2 ответа

Решение

Самостоятельно, newtypes являются бесплатными. Применение их конструктора или сопоставление с ними по шаблону обходится без затрат.

При использовании в качестве параметра для других типов, например [T] представление [T] точно так же, как тот, для [T'] если T это newtype forT`. Таким образом, нет никаких потерь в производительности.

Тем не менее, я вижу два основных предостережения.

newtypeи случаи

Первый, newtype часто используется для введения новых instanceс типами классов. Ясно, что когда они определены пользователем, нет гарантии, что они будут стоить столько же, сколько и исходные экземпляры. Например, при использовании

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

сравнивая два Op Int будет стоить немного больше, чем сравнение Int, поскольку аргументы нужно поменять местами. (Я здесь пренебрегаю оптимизацией, которая может сделать эту стоимость бесплатной, когда они сработают.)

newtypes используется в качестве аргументов типа

Второй момент более тонкий. Рассмотрим следующие две реализации идентичности [Int] -> [Int]

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

Первый имеет постоянную стоимость. Второй имеет линейную стоимость (при условии отсутствия триггеров оптимизации). Умный программист должен предпочесть первую реализацию, которую также проще написать.

Предположим теперь мы вводим newtypes только для типа аргумента:

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

Мы больше не можем использовать реализацию с постоянными затратами из-за ошибки типа. Реализация линейной стоимости все еще работает и является единственным вариантом.

Теперь это довольно плохо. Входное представление для [Op Int] точно, постепенно, то же самое для [Int], Тем не менее, система типов запрещает нам эффективно выполнять идентификацию!

Чтобы преодолеть эту проблему, безопасное принуждение было введено в Haskell.

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

Магия coerce функция, при определенных гипотезах, удаляет или вставляет newtypes по мере необходимости, чтобы согласовать тип, даже внутри других типов, как для [Op Int] выше. Кроме того, это функция с нулевой стоимостью.

Обратите внимание, что coerce работает только при определенных условиях (компилятор проверяет их). Одним из них является то, что newtype конструктор должен быть виден: если модуль не экспортируется Op :: a -> Op a ты не можешь принуждать Op Int в Int или наоборот. Действительно, если модуль экспортирует тип, но не конструктор, было бы неправильно делать конструктор доступным в любом случае через coerce, Это делает идиому "умных конструкторов" по-прежнему безопасным: модули по-прежнему могут применять сложные инварианты через непрозрачные типы.

Не имеет значения, насколько глубоко скрыт новый тип в стеке (полностью) параметрических типов. Во время выполнения значения v :: Speed а также w :: Double полностью неразличимы - обертка стирается компилятором, так что даже v на самом деле просто указатель на одно 64-битное число с плавающей точкой в ​​памяти. Хранится ли этот указатель в списке или в дереве или что-либо еще, не имеет значения. getSpeed не работает и не будет отображаться во время выполнения вообще.

Итак, что я подразумеваю под "полностью параметрическим"? Дело в том, что новые типы могут иметь значение во время компиляции через систему типов. В частности, они могут управлять разрешением экземпляра, поэтому новый тип, который вызывает другой метод класса, может, безусловно, иметь худшую (или, как легко, лучшую!) Производительность, чем упакованный тип. Например,

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

эта реализация довольно медленная, потому что она использует ленивый список (и выполняет поиск в нем снова и снова) для запоминания. С другой стороны,

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)

это fib намного быстрее, потому что благодаря тому, что ввод ограничен небольшим диапазоном, возможно строго распределить все результаты и сохранить их в быстром поисковом массиве O (1), не требуя ленивости позвоночника.

Это, конечно, применяется снова, независимо от того, в какой структуре вы храните числа. Но разная производительность достигается только потому, что вызываются разные экземпляры методов - во время выполнения это означает просто, совершенно разные функции.

Теперь полностью параметрический конструктор типов должен иметь возможность хранить значения любого типа. В частности, он не может налагать какие-либо ограничения класса на содержащиеся данные и, следовательно, также не вызывать какие-либо методы класса. Поэтому такого рода разница в производительности не может произойти, если вы просто имеете дело с общим [a] списки или Map Int a карты. Однако это может произойти, когда вы имеете дело с ГАДЦ. В этом случае даже фактическое расположение памяти может быть совершенно другим, например, с

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

может позволить вам хранить Double ценности более эффективно, чем Speed значения, потому что первый может быть сохранен в оптимизированном кеше распакованном массиве. Это возможно только потому, что UnboxArray Конструктор не полностью параметрический.

Другие вопросы по тегам