Pull to refresh

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

Reading time 7 min
Views 4.8K
НовыйТип (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 о новыхТипах станет чуть понятней!
Tags:
Hubs:
+13
Comments 2
Comments Comments 2

Articles