Großmacht Newtypes

Published on October 15, 2018

Großmacht Newtypes

    Ein neuer Typ ist eine spezialisierte Datentypdeklaration. So dass es nur einen Konstruktor und ein Feld enthält.

    newtype Foo a = Bar a
    newtype Id = MkId Word
    


    Häufige Anfängerfragen


    Was ist der Unterschied vom Datentyp von Daten?

    data Foo a = Bar a
    data Id = MkId Word
    

    Die hauptsächliche Besonderheit eines neuen Typs besteht darin, dass er aus denselben Teilen besteht wie sein einziges Feld. Genauer gesagt unterscheidet es sich vom Original auf der Typebene, hat jedoch die gleiche Speicherdarstellung und wird streng (nicht träge) berechnet.
    Kurz gesagt, ein neuer Typ ist aufgrund seiner Darstellung effizienter.

    Ja, es bedeutet nichts für mich ... Ich werde Daten verwenden. Nun ja
    , am Ende können Sie immer die -funpack-strict-fields :) -Erweiterung für strenge (nicht faule) Felder aktivieren oder angeben

    data Id = MkId !Word
    

    Die Kraft des neuen Typs ist jedoch nicht auf die Effizienz der Berechnungen beschränkt. Sie sind viel stärker!

    3 neue Rollen




    Implementierung verbergen


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

    Ein neuer Typ unterscheidet sich vom ursprünglichen, nur intern verwendeten Word .
    Wir verstecken aber den MkId- Konstruktor außerhalb des Moduls.

    Implementierung der Distribution


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

    Obwohl dies nicht im Haskell2010-Standard enthalten ist, können Sie dank der Erweiterung der generalisierten newTypes-Ausgabe automatisch auf das Verhalten neuer Typen schließen, das dem Verhalten des internen Felds entspricht. In unserem Fall ist das Verhalten von Eq Id und Num Id dasselbe wie das von Eq Word und Num Word .

    Durch die Ausweitung der verfeinerten Eliminierung ( DerivingVia ) kann viel mehr erreicht werden , aber dazu später mehr.

    Implementierung der Wahl


    Trotz Ihres eigenen Konstruktors können Sie in einigen Fällen Ihre eigene interne Darstellung verwenden.

    Aufgabe


    Es gibt eine Liste von ganzen Zahlen. Finden Sie den Maximal- und Gesamtbetrag für nur einen Durchgang durch die Liste.
    Und verwenden Sie nicht die Pakete foldl und folds .

    Typische Antwort


    Natürlich, klapp ! :)

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

    Und die endgültige Funktion wird wie folgt beschrieben:

    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)
    -}
    

    Wenn Sie genau hinschauen, sehen Sie auf beiden Seiten ähnliche Vorgänge: Nur el `max` m und el + s . In beiden Fällen - Mapping und Binäroperation. Und die leeren Elemente sind Nothing und 0 .

    Ja, das sind Monoide!

    Monoid und Halbgruppe mehr
    Eine Halbgruppe ist eine Eigenschaft einer assoziativen Binäroperation.

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

    Ein Monoid ist eine Eigenschaft einer assoziativen Operation (dh einer Halbgruppe).

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

    Das hat ein leeres Element, das kein Element nach rechts oder links ändert

    x ⋄ empty  ==  x  ==  empty ⋄ x
    


    Sowohl max als auch (+) sind assoziativ, beide haben leere Elemente - Nothing und 0 .

    Und die Vereinigung der Kartierung von Monoiden mit der Faltung ist die gleiche Faltbare !

    Faltbare mehr Details
    Напомним определение сворачиваемости:

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


    Wenden wir das Rollover-Verhalten auf max und (+) an . Wir können nicht mehr als eine Implementierung arrangieren Monoid ein Wort . Es ist Zeit, die Option newtype zu verwenden !

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

    Es ist notwendig, eine Bemerkung zu machen.

    Tatsache ist, dass wir , um ein Monoid für den Datentyp Max zu sein , ein minimales Element benötigen, das heißt, dass ein leeres Element existiert. Ein Monoid kann also nur ein begrenztes Maximum sein .

    Theoretisch korrektes Monoid des maximalen Elements
    newtype Max a = Max a
    instance Ord a => Semigroup (Max a)
    instance Bounded a => Monoid (Max a)
    


    Irgendwie müssen wir also unseren Datentyp konvertieren, damit ein leeres Element angezeigt wird und wir die Gerinnung verwenden können.

    -- 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)
    

    Das konjugierte Element macht aus einer Halbgruppe vielleicht ein Monoid!

    Liberalisierung der Beschränkungen in neuen Versionen von 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)
    


    Abklingzeit-Antwort


    Nun wollen wir den Code mit dem Rollover und den Pfeilen aktualisieren.
    Denken Sie daran, dass (.) Nur eine funktionale Zusammensetzung ist:

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

    Und denk dran, dass fmap ein Funktor ist:

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

    und seine Implementierung für Vielleicht ist gerade oben beschrieben.

    Pfeil mehr Details
    Стрелки — это свойства некоторых функций, которые позволяют работать с ними блок-схемно.
    Более детально, можно посмотреть тут: 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'))

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

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

    Die gesamte vereinigende Funktion erhielt die Form:

    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))
    -}
    

    Es stellte sich sehr kurz heraus!

    Es ist jedoch immer noch anstrengend, Daten von verschachtelten Typen zu brechen und zu brechen!
    Sie können noch reduzieren und wir helfen Ihnen bei der ressourcenlosen Zwangskonvertierung!

    Sichere ressourcenfreie erzwungene Konvertierung und Rollentypen


    Es gibt eine Funktion aus dem Paket Unsafe.Coerce - unsafeCoerce

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

    Die Funktion konvertiert den Typ zwangsweise: von a nach b .
    Die Funktion ist im Wesentlichen magisch. Sie weist den Compiler an, Daten vom Typ a als Typ b zu betrachten , ohne die Konsequenzen dieses Schritts zu berücksichtigen.

    Es kann verwendet werden, um verschachtelte Typen zu konvertieren, aber Sie müssen sehr vorsichtig vorgehen.

    Im Jahr 2014 kam es zu einer Revolution mit einem neuen Typ , nämlich einer sicheren, ressourcenlosen, erzwungenen Umstellung!

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

    Diese Funktion hat eine neue Ära in der Arbeit mit newtype eröffnet .

    Der Zwangsumwandler arbeitet mit Typen, die im Speicher die gleiche Struktur haben. Es sieht aus wie ein Klassentyp, aber tatsächlich konvertiert GHC Typen während der Kompilierung und es ist nicht möglich, Instanzen unabhängig zu bestimmen.
    Die Data.Coerce.coerce- Funktion ermöglicht eine ressourcenfreie Typkonvertierung. Hierzu benötigen wir jedoch Zugriff auf Typkonstruktoren .

    Vereinfachen Sie jetzt unsere Funktion:

    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)
    

    Wir haben die Routine vermieden, verschachtelte Typen herauszuziehen, ohne Ressourcen mit nur einer Funktion aufzuwenden.

    Rollen verschachtelter Datentypen


    Mit der Coerce- Funktion können wir verschachtelte Typen zwangsweise konvertieren.
    Aber ist es notwendig, diese Funktion so umfassend zu nutzen?

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

    Semantisch ist es absurd, von Sorted (Down a) zu Sorted a zu konvertieren . Sie können jedoch versuchen:


    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)
    

    Alles andere als die richtige Antwort ist Just (Down 3) .
    Um das falsche Verhalten zu unterbinden, wurden Typrollen eingeführt.

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

    Lass es uns jetzt versuchen:

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

    Viel besser

    Insgesamt gibt es 3 Rollen ( Typrolle ):

    • gegenständlich - gleichwertig bei gleicher Darstellung
    • nominal - muss genau vom selben Typ sein
    • Phantom - hängt nicht vom tatsächlichen Inhalt ab. Äquivalent zu allem

    In den meisten Fällen ist der Compiler intelligent genug, um die Rolle des Typs aufzudecken, aber es kann geholfen werden.

    Spezifiziertes Injection DerivingVia-Verhalten


    Durch die Erweiterung der Sprache DerivingVia , die Verbreitung der Rolle verbessert ein newtype .

    Beginnend mit GHC 8.6, das kürzlich veröffentlicht wurde, ist diese neue Erweiterung erschienen.

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

    Wie Sie sehen, wird das Verhalten des Typs dank der Klarstellung der Ausgabemethode automatisch abgeleitet.
    DerivingVia kann auf jeden Typ angewendet werden, der Coercible unterstützt und was wichtig ist - ganz ohne den Verbrauch von Ressourcen!

    Noch mehr, DerivingVia kann angewendet werden , nicht nur zu einem newtype , sondern auch auf jede Art von isomorph , wenn sie Generika unterstützen Generics und Zwangsbekehrungen coercible .

    Schlussfolgerungen


    Types newtype - eine mächtige Kraft, die den Code erheblich vereinfacht und verbessert, die Routine beseitigt und den Ressourcenverbrauch senkt.

    Originalübersetzung : Die große Kraft der Newtypes (Hiromi Ishii)

    PS Ich denke, nach diesem Artikel, der vor mehr als einem Jahr veröffentlicht wurde [nicht meiner], wird Haskells Newtype-Magie über neue Typen ein wenig deutlicher!