Великая сила newtypes

    НовыйТип (newtype) — это специализированное объявление типа данных. Такое, что содержит лишь один конструктор и поле.

    newtype Foo a = Bar a
    newtype Id = MkId Word
    


    Типичные вопросы новичка


    В чём же отличие от data типа данных?

    data Foo a = Bar a
    data Id = MkId Word
    

    Главная специфика newtype состоит в том, что он состоит из тех же частей, что и его единственное поле. Более точно — отличаясь от оригинала на уровне типа, но имеет такое же представление в памяти, да и вычисляется строго (не лениво).
    Если вкратце — newtype более эффективны благодаря своему представлению.

    Да это ничего не значит для меня… Буду использовать data
    Не, ну в конце-концов, всегда можно включить расширение -funpack-strict-fields :) для строгих(не ленивых) полей или указать прямо

    data Id = MkId !Word
    

    Всё же сила newtype не ограничивается лишь эффективностью вычислений. Они значительно сильнее!

    3 роли newtype




    Имплементация сокрытия


    module Data.Id (Id()) where
    newtype Id = MkId Word
    

    newtype отличаясь от оригинала, внутренне всего лишь Word.
    Но мы скрываем конструктор MkId вне модуля.

    Имплементация распространения


    {-# LANGUAGE GeneralizedNewtypeDeriving #-}
    newtype Id = MkId Word deriving (Num, Eq)
    

    Хотя этого нет в стандарте Haskell2010, благодаря расширению вывдения обобщённых новыхТипов, можно автоматически вывести поведение newtype таким же, как и поведение внутреннего поля. В нашем случае поведение Eq Id и Num Id таким же, как и Eq Word и Num Word.

    Значительно большего можно добиться благодаря расширению уточнённого выведения (DerivingVia), но об этом чуть позже.

    Имплементация выбора


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

    Задача


    Имеется список целых чисел. Найти максимум и общую сумму за всего один проход по списку.
    И не пользоваться пакетами foldl и folds.

    Типичный ответ


    Конечно, fold! :)

    foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
    {-
    -- instance Foldable []
    foldr :: (a -> b -> b) -> b -> [a] -> b
    -}
    

    И, итоговая функция описывается так:

    aggregate :: [Integer] -> (Maybe Integer, Integer)
    aggregate = foldr
          (\el (m, s) -> (Just el `max` m, el + s))
          (Nothing, 0)
    
    {-
    ghci> aggregate [1, 2, 3, 4]
    (Just 4, 10)
    -}
    

    Если присмотреться, можно увидеть подобные операции по обе стороны: Just el `max` m и el + s. В обоих случаях — мэппинг и бинарная операция. И пустые элементы — Nothing и 0.

    Да, это моноиды!

    Monoid и Semigroup детальнее
    Полугруппа — это свойство ассоциативной бинарной операции

    x ⋄ (y ⋄ z) == (x ⋄ y) ⋄ z
    

    Моноид — это свойство ассоциативной операции (то есть полугруппы)

    x ⋄ (y ⋄ z) == (x ⋄ y) ⋄ z
    

    которое имеет пустой элемент, не меняющий любой элемент ни справа, ни слева

    x ⋄ empty  ==  x  ==  empty ⋄ x
    


    Оба max и (+) — ассоциативны, оба имеют пустые элементы — Nothing и 0.

    А объединение мэппинга моноидов вместе со свёрткой — это же Foldable(сворачиваемость)!

    Foldable детальнее
    Напомним определение сворачиваемости:

    class Foldable t where 
          foldMap :: (Monoid m) => (a -> m) -> t a -> m
          ...
    


    Давайте применим поведение сворачиваемости к max и (+). Мы сможем организовать не более одной реализации моноида Word. Самое время воспользоваться имплементацией выбора newtype!

    {-# LANGUAGE GeneralizedNewtypeDeriving #-}
    
    -- already in Data.Semigroup & Data.Monoid
    
    newtype Sum a = Sum {getSum :: a}
        deriving (Num, Eq, Ord)
    
    instance (Num a, Ord a) => Semigroup (Sum a) where
        (<>) = (+)
    
    instance (Num a, Ord a) => Monoid (Sum a) where
        mempty = Sum 0
    
    newtype Max a = Max {getMax :: a}
        deriving (Num, Eq, Ord)
    
    instance (Num a, Ord a) => Semigroup (Max a) where
        (<>) = max
    

    Необходимо сделать ремарку.

    Дело в том, что для того, чтобы быть моноидом для типа данных Max a, нам необходим минимальный элемент, то есть чтоб существовал пустой элемент. А значит, моноидом может быть лишь ограниченный Max a.

    Теоретически правильный моноид максимального элемента
    newtype Max a = Max a
    instance Ord a => Semigroup (Max a)
    instance Bounded a => Monoid (Max a)
    


    Так что нам как-то придётся конвертировать наш тип данных для того, чтобы появился пустой элемент и мы могли бы использовать свёртываемость.

    -- already in Prelude
    data Maybe a = Nothing | Just a
    
    instance Semigroup a => Semigroup (Maybe a) where
        Nothing <> b = b
        b <> Nothing = b
        (Just a) <> (Just b) = Just (a <> b)
    
    instance Semigroup a => Monoid (Maybe a) where
        mempty = Nothing
    
    -- ------
    instance Functor Maybe where
        fmap _ Nothing = Nothing
        fmap f (Just b) = Just (f b)
    

    Сопряжённый элемент Maybe превращает полугруппу в моноид!

    Либерализация ограничений в свежих версиях GHC
    Ещё в GHC 8.2 требовался моноид в ограничении типа

    instance Monoid a => Monoid (Maybe a)
    

    а значит нам был необходим ещё один новыйТип:

    -- already in Data.Semigroup & Data.Monoid
    
    newtype Option a = Option {getOption :: Maybe a}
        deriving (Eq, Ord, Semigroup)
    
    instance (Ord a, Semigroup a) => Monoid (Option a) where
        mempty = Option Nothing
    

    И значительно проще уже в GHC 8.4, где необходима лишь полугруппа в ограничении типа, и даже нет необходимости в создании типа Опция.

    instance Semigroup a => Monoid (Maybe a)
    


    Ответ с использованием сворачиваемости


    Что ж, теперь обновим код, используя сворачиваемость и стрелки.
    Вспоминаем, что (.) — всего лишь функциональная композиция:

     (.) :: (b -> c) -> (a -> b) -> a -> c
     f . g = \x -> f (g x)

    И вспоминаем, что fmap — функтор:

    fmap :: Functor f => (a -> b) -> f a -> f b

    а её реализация для Maybe описана чуть выше.

    Arrow детальнее
    Стрелки — это свойства некоторых функций, которые позволяют работать с ними блок-схемно.
    Более детально, можно посмотреть тут: Arrows: A General Interface to Computation
    В нашем случае мы используем Стрелки функции
    То есть

    instance Arrow (->)

    Мы будем использовать функции:

    (***) :: Arrow a => a b c -> a b' c' -> a (b, b') (c, c')
    (&&&) :: Arrow a => a b c -> a b c' -> a b (c, c')

    Для нашего случая
    a b c   ==   (->) b c   ==   b -> c

    И, соответственно, подпись наших функций сокращается до:

    (***) :: (b -> c) -> (b' -> c') -> ((b, b') -> (c, c'))
    (&&&) :: (b -> c) -> (b -> c') -> (b -> (c, c'))

    Или совсем простыми словами, функция (***) объединяет две функции с одним аргументом(и одним выходным типом) в функцию с работой пары аргументов на входе, и на выходе, соответственно пара выходных типов.

    Функция (&&&) — это урезанная версия (***), где тип входного аргументов двух функций одинаков, и на входе у нас не пара аргументов, а один аргумент.

    Итого, объединяющая функция приобрела вид:

    import Data.Semigroup 
    import Data.Monoid
    import Control.Arrow
    
    aggregate :: [Integer] -> (Maybe Integer, Integer)
    aggregate = 
          (fmap getMax *** getSum)
          . (foldMap (Just . Max &&& Sum))
    
    {-
    -- for GHC 8.2
    aggregate = 
         (fmap getMax . getOption *** getSum)
         . (foldMap (Option . Just . Max &&& Sum))
    -}
    

    Получилось очень кратко!

    Но, всё ещё утомительно оборачивать и выворачивать данные из вложенных типов!
    Можно ещё сократить, и нам поможет безресурсное принудительное преобразование!

    Безопасное безресурсное принудительное преобразование и роли типов


    Существует функция из пакета Unsafe.CoerceunsafeCoerce

    import Unsafe.Coerce(unsafeCoerce)
    unsafeCoerce :: a -> b
    

    Функция принудительно небезопасно преобразовывает тип: из a в b.
    По сути функция — магическая, она указывает компилятору считать данные типа a типом b, без учёта последствий этого шага.

    Её можно использовать для преобразования вложенных типов, но действовать нужно очень осторожно.

    В 2014 году произошла революция с newtype, а именно появилось безопасное безресурсное принудительное преобразование!

    import Data.Coerce(coerce)
    coerce :: Coercible a b => a -> b
    

    Эта функция открыла новую эру в работе с newtype.

    Принудительный преобразователь Coercible работает с типами, которые имеют одинаковую структуру в памяти. Он выглядит как класс-тип, но на самом деле GHC преобразовывает типы во время компиляции и невозможно самостоятельно определить инстансы.
    Функция Data.Coerce.coerce позволяет безресурсно преобразовать типы, но для этого нам нужно иметь доступ к конструкторам типа.

    Теперь упростим нашу функцию:

    import Data.Semigroup 
    import Data.Monoid
    import Control.Arrow
    import Data.Coerce
    
    aggregate :: [Integer] -> (Maybe Integer, Integer)
    aggregate = 
          coerce . (foldMap (Just . Max &&& Sum))
    
    -- coerce :: (Maybe (Max Integer), Sum Integer) -> (Maybe Integer, Integer)
    

    Мы избежали рутины вытаскивания вложенных типов, сделали это не тратя ресурсов всего лишь одной функцией.

    Роли вложенных типах данных


    С функцией coerce мы можем принудительно преобразовывать любые вложенные типы.
    Но нужно ли столь широко использовать эту функцию?

    -- already in Data.Ord
    -- Down a - reversed order
    newtype Down a = Down a
        deriving (Eq, Show)
    
    instance Ord a => Ord (Down a) where
        compare (Down x) (Down y) = y `compare` x
    
    import Data.List(sort)
    -- Sorted
    data Sorted a = Sorted [a]
        deriving (Show, Eq, Ord)
    
    fromList2Sorted :: Ord a => [a] -> Sorted a
    fromList2Sorted = Sorted . sort
    
    -- minimum: O(1) !
    minView :: Sorted a -> Maybe a
    minView (Sorted []) = Nothing
    minView (Sorted (a : _))  = Just a
    

    Семантически, абсурдно преобразовывать в Sorted a из Sorted (Down a).
    Тем не менее, попробовать можно:

    ghci> let h = fromList2Sorted [1,2,3] :: Sorted Int
    ghci> let hDown = fromList2Sorted $ fmap Down [1,2,3] :: Sorted (Down Int)
    ghci> minView h
    Just (Down 1)
    ghci> minView (coerce h :: Sorted (Down Int))
    Just (Down 1)
    
    ghci> minView hDown
    Just (Down 3)
    

    Всё бы ничего, но правильный ответ — Just (Down 3).
    Именно для того, чтобы отсечь неверное поведение, были введены роли типов.

    {-# LANGUAGE RoleAnnotations #-}
    
    type role Sorted nominal
    

    Попробуем теперь:

    ghci> minView (coerce h :: Sorted (Down Int))
    error: Couldn't match type ‘Int’ with ‘Down Int’
            arising from a use of ‘coerce’
    

    Значительно лучше!

    Всего существует 3 роли (type role):

    • representational — эквивалентны, если одинаково представление
    • nominal — должны иметь совершенно одинаковый тип
    • phantom — не зависит от реального содержания. Эквивалентен чему угодно

    В большинстве случаем компилятор достаточно умён, чтобы выявить роль типа, но ему можно помочь.

    Уточнённое выведение поведение DerivingVia


    Благодаря расширению языка DerivingVia, улучшилась роль распространения newtype.

    Начиная с GHC 8.6, который вышел в свет недавно, появилось это новое расширение.

    {-# LANGUAGE DerivingVia #-}
    newtype Id = MkId Word deriving (Semigroup, Monoid) via Max Word
    

    Как видно, автоматически выведено поведение типа благодаря уточнению как выводить.
    DerivingVia можно применять к любому типу, который поддерживает Coercible и что важно — совершенно без потребления ресурсов!

    Даже более, DerivingVia можно применять не только к newtype, но и к любым изоморфным типам, если они поддерживают генерики Generics и принудительное преобразование Coercible.

    Выводы


    Типы newtype — мощная сила, которая значительно упрощает и улучшает код, избавляет от рутины и уменьшает потребление с ресурсов.

    Оригинал перевода: The Great Power of newtypes (Hiromi Ishii)

    P.S. Думаю, после этой статьи, вышедшая более года назад [не моя] статья Магия newtype в Haskell о новыхТипах станет чуть понятней!
    • +13
    • 2,9k
    • 2
    Поделиться публикацией

    Комментарии 2

      0

      Спасибо за перевод! Про безопасное приведение очень полезная информация.

        0

        Спасибо.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое