Wie funktioniert das Ableiten in Haskell?

104

Algebraische Datentypen (ADT) in Haskell kann automatisch Instanzen einiger geworden typeclasse s (wieShow,Eq) durch Ableiten von ihnen.

data  Maybe a  =  Nothing | Just a
  deriving (Eq, Ord)

Meine Frage ist, wie funktioniert das deriving, dh woher weiß Haskell, wie die Funktionen der abgeleiteten Typklasse für das abgeleitete ADT implementiert werden?

Warum ist es derivingnur auf bestimmte Typenklassen beschränkt? Warum kann ich keine eigene Typklasse schreiben, die abgeleitet werden kann?

Abhinav Sarkar
quelle

Antworten:

75

Die kurze Antwort lautet: Magie :-). Dies bedeutet, dass die automatische Ableitung in die Haskell-Spezifikation integriert ist und jeder Compiler sie auf seine eigene Weise implementieren kann. Es gibt jedoch viel Arbeit daran, es erweiterbar zu machen.

Ableiten ist ein Tool für Haskell, mit dem Sie Ihre eigenen Ableitungsmechanismen schreiben können.

GHC stellte früher eine ableitbare Typklassenerweiterung namens Generic Classes bereit , wurde jedoch selten verwendet, da sie etwas schwach war. Das wurde nun herausgenommen und es wird daran gearbeitet, einen neuen generischen Ableitungsmechanismus zu integrieren, wie in diesem Dokument beschrieben: http://www.dreixel.net/research/pdf/gdmh.pdf

Weitere Informationen hierzu finden Sie unter:

sclv
quelle
2
Siehe auch StandaloneDerivingim ghc Handbuch und in haskellwiki
AndrewC
1
Nur zu Ihrer Information, die Magie ist unter haskell.org/onlinereport/haskell2010/haskellch11.html klar spezifiziert .
Wong Jia Hau
19

Aus dem Haskell 98-Bericht:

Die einzigen Klassen im Prelude, für die abgeleitete Instanzen zulässig sind, sind Gl., Ord, Enum, Bounded, Show und Read ...

Hier ist die Beschreibung, wie diese Typklassen abgeleitet werden: http://www.haskell.org/onlinereport/derived.html#derived-appendix

tibbe
quelle
5

Es ist möglich, Template Haskell zu verwenden, um Instanzdeklarationen auf ähnliche Weise wie Ableitungsklauseln zu generieren.

Das folgende Beispiel wurde schamlos aus dem Haskell-Wiki gestohlen :

In diesem Beispiel verwenden wir den folgenden Haskell-Code

$(gen_render ''Body)

um die folgende Instanz zu erzeugen:

instance TH_Render Body where
  render (NormalB exp) = build 'normalB exp
  render (GuardedB guards) = build 'guardedB  guards

Die gen_renderobige Funktion ist wie folgt definiert. (Beachten Sie, dass sich dieser Code in einem von der obigen Verwendung getrennten Modul befinden muss.)

-- Generate an intance of the class TH_Render for the type typName
gen_render :: Name -> Q [Dec]
gen_render typName =
  do (TyConI d) <- reify typName -- Get all the information on the type
     (type_name,_,_,constructors) <- typeInfo (return d) -- extract name and constructors                  
     i_dec <- gen_instance (mkName "TH_Render") (conT type_name) constructors
                      -- generation function for method "render"
                      [(mkName "render", gen_render)]
     return [i_dec]  -- return the instance declaration
             -- function to generation the function body for a particular function
             -- and constructor
       where gen_render (conName, components) vars 
                 -- function name is based on constructor name  
               = let funcName = makeName $ unCapalize $ nameBase conName 
                 -- choose the correct builder function
                     headFunc = case vars of
                                     [] -> "func_out"
                                     otherwise -> "build" 
                      -- build 'funcName parm1 parm2 parm3 ...
                   in appsE $ (varE $ mkName headFunc):funcName:vars -- put it all together
             -- equivalent to 'funcStr where funcStr CONTAINS the name to be returned
             makeName funcStr = (appE (varE (mkName "mkName")) (litE $ StringL funcStr))

Welches verwendet die folgenden Funktionen und Typen.

Zuerst einige Typensynonyme, um den Code besser lesbar zu machen.

type Constructor = (Name, [(Maybe Name, Type)]) -- the list of constructors
type Cons_vars = [ExpQ] -- A list of variables that bind in the constructor
type Function_body = ExpQ 
type Gen_func = Constructor -> Cons_vars -> Function_body
type Func_name = Name   -- The name of the instance function we will be creating
-- For each function in the instance we provide a generator function
-- to generate the function body (the body is generated for each constructor)
type Funcs = [(Func_name, Gen_func)]

Die hauptsächliche wiederverwendbare Funktion. Wir übergeben ihm die Liste der Funktionen, um die Funktionen der Instanz zu generieren.

-- construct an instance of class class_name for type for_type
-- funcs is a list of instance method names with a corresponding
-- function to build the method body
gen_instance :: Name -> TypeQ -> [Constructor] -> Funcs -> DecQ
gen_instance class_name for_type constructors funcs = 
  instanceD (cxt [])
    (appT (conT class_name) for_type)
    (map func_def funcs) 
      where func_def (func_name, gen_func) 
                = funD func_name -- method name
                  -- generate function body for each constructor
                  (map (gen_clause gen_func) constructors)

Eine Hilfsfunktion der oben genannten.

-- Generate the pattern match and function body for a given method and
-- a given constructor. func_body is a function that generations the
-- function body
gen_clause :: (Constructor -> [ExpQ] -> ExpQ) -> Constructor -> ClauseQ
gen_clause func_body data_con@(con_name, components) = 
      -- create a parameter for each component of the constructor
   do vars <- mapM var components
      -- function (unnamed) that pattern matches the constructor 
      -- mapping each component to a value.
      (clause [(conP con_name (map varP vars))]
            (normalB (func_body data_con (map varE vars))) [])
       -- create a unique name for each component. 
       where var (_, typ) 
                 = newName 
                   $ case typ of 
                     (ConT name) -> toL $ nameBase name
                     otherwise   -> "parm"
               where toL (x:y) = (toLower x):y

unCapalize :: [Char] -> [Char]
unCapalize (x:y) = (toLower x):y

Und ein geliehener Hilfecode aus Syb III / replib 0.2.

typeInfo :: DecQ -> Q (Name, [Name], [(Name, Int)], [(Name, [(Maybe Name, Type)])])
typeInfo m =
     do d <- m
        case d of
           d@(DataD _ _ _ _ _) ->
            return $ (simpleName $ name d, paramsA d, consA d, termsA d)
           d@(NewtypeD _ _ _ _ _) ->
            return $ (simpleName $ name d, paramsA d, consA d, termsA d)
           _ -> error ("derive: not a data type declaration: " ++ show d)

     where
        consA (DataD _ _ _ cs _)    = map conA cs
        consA (NewtypeD _ _ _ c _)  = [ conA c ]

        {- This part no longer works on 7.6.3
        paramsA (DataD _ _ ps _ _) = ps
        paramsA (NewtypeD _ _ ps _ _) = ps
        -}

        -- Use this on more recent GHC rather than the above
        paramsA (DataD _ _ ps _ _) = map nameFromTyVar ps
        paramsA (NewtypeD _ _ ps _ _) = map nameFromTyVar ps

        nameFromTyVar (PlainTV a) = a
        nameFromTyVar (KindedTV a _) = a


        termsA (DataD _ _ _ cs _) = map termA cs
        termsA (NewtypeD _ _ _ c _) = [ termA c ]

        termA (NormalC c xs)        = (c, map (\x -> (Nothing, snd x)) xs)
        termA (RecC c xs)           = (c, map (\(n, _, t) -> (Just $ simpleName n, t)) xs)
        termA (InfixC t1 c t2)      = (c, [(Nothing, snd t1), (Nothing, snd t2)])

        conA (NormalC c xs)         = (simpleName c, length xs)
        conA (RecC c xs)            = (simpleName c, length xs)
        conA (InfixC _ c _)         = (simpleName c, 2)

        name (DataD _ n _ _ _)      = n
        name (NewtypeD _ n _ _ _)   = n
        name d                      = error $ show d

simpleName :: Name -> Name
simpleName nm =
   let s = nameBase nm
   in case dropWhile (/=':') s of
        []          -> mkName s
        _:[]        -> mkName s
        _:t         -> mkName t
Lii
quelle