Prüft, ob ein Wert entspricht einem Konstruktor

Question

sagen, dass ich ein Datentyp wie so haben:

data NumCol = Empty | 
       Single Int | 
       Pair Int Int | 
       Lots [Int] 

Jetzt möchte ich die Elemente herauszufiltern einen bestimmten Konstruktor aus einem [NumCol] entsprechen. Ich kann es schreiben, sagen wir, Pair:

get_pairs :: [NumCol] -> [NumCol] 
get_pairs = filter is_pair 
    where is_pair (Pair _ _) = True 
      is_pair _ = False 

Dies funktioniert, aber es ist nicht generisch. Ich habe eine eigene Funktion für is_single zu schreiben, is_lots usw.

ich stattdessen möchte ich schreiben könnte:

get_pairs = filter (== Pair) 

Das funktioniert aber nur für Typkonstruktoren die keine Argumente haben (das heißt Empty).

Die Frage ist also, wie kann ich eine Funktion schreiben, die einen Wert und einen Konstruktor nimmt, und gibt zurück, ob der Wert dem Konstruktor entspricht?

Answer 1

Mindestens get_pairs selbst kann relativ einfach Verständnis unter Verwendung einer Liste definiert werden, anstatt zu filtern:

get_pairs xs = [x | x@Pair {} <- xs] 

Für eine allgemeinere Lösung passenden Bauer, Sie Prismen vom lens Paket verwenden können:

{-# LANGUAGE TemplateHaskell #-} 

import Control.Lens 
import Control.Lens.Extras (is) 

data NumCol = Empty | 
       Single Int | 
       Pair Int Int | 
       Lots [Int] 

-- Uses Template Haskell to create the Prisms _Empty, _Single, _Pair and _Lots 
-- corresponding to your constructors 
makePrisms ''NumCol 

get_pairs :: [NumCol] -> [NumCol] 
get_pairs = filter (is _Pair) 

Answer 2

Stichworte von getaggten Gewerkschaften sollten erstklassige Werte sein, und mit ein bisschen Mühe sind sie.

Schmu Alarm:

{-# LANGUAGE GADTs, DataKinds, KindSignatures, 
    TypeFamilies, PolyKinds, FlexibleInstances, 
    PatternSynonyms 
#-} 

Erster Schritt: Typ-Level-Versionen der Tags definieren.

Schritt zwei: Definieren Sie Zeugen auf Werteebene für die Darstellbarkeit der Tags auf Textebene. Richard Eisenbergs Singletons-Bibliothek wird dies für Sie tun. Ich meine etwas in der Art:

data Tag :: TagType -> * where 
    EmptyT :: Tag EmptyTag 
    SingleT :: Tag SingleTag 
    PairT :: Tag PairTag 
    LotsT :: Tag LotsTag 

Und jetzt können wir sagen, welche Sachen, die wir erwarten, mit einem gegebenen Tag verbunden zu finden.

type family Stuff (t :: TagType) :: * where 
    Stuff EmptyTag =() 
    Stuff SingleTag = Int 
    Stuff PairTag = (Int, Int) 
    Stuff LotsTag = [Int] 

So können wir die Art du erster Gedanke von

data NumCol :: * where 
    (:&) :: Tag t -> Stuff t -> NumCol 

und PatternSynonyms das Verhalten zu erholen verwenden Refactoring Sie im Sinn hatte:

pattern Empty  = EmptyT :& () 
pattern Single i = SingleT :& i 
pattern Pair i j = PairT :& (i, j) 
pattern Lots is = LotsT :& is 

So was passiert ist, dass jeder Konstruktor für NumCol hat sich in ein Tag verwandelt, das nach der Art des Tags indiziert ist. Das heißt, Konstruktortags leben nun getrennt von den übrigen Daten, synchronisiert durch einen gemeinsamen Index, der sicherstellt, dass das mit einem Tag verbundene Material mit dem Tag selbst übereinstimmt.

Aber wir können über Tags allein sprechen.

data Ex :: (k -> *) -> * where -- wish I could say newtype here 
    Witness :: p x -> Ex p 

Nun Ex Tag, ist die Art der "Laufzeit-Tags mit einem Typ-Ebene Pendant". Es hat eine Eq Instanz

instance Eq (Ex Tag) where 
    Witness EmptyT == Witness EmptyT = True 
    Witness SingleT == Witness SingleT = True 
    Witness PairT == Witness PairT = True 
    Witness LotsT == Witness LotsT = True 
    _    == _    = False 

Darüber hinaus können wir den Tag eines NumCol leicht extrahieren.

numColTag :: NumCol -> Ex Tag 
numColTag (n :& _) = Witness n 

Und das erlaubt uns, Ihre Spezifikation zu erfüllen.

filter ((Witness PairT ==) . numColTag) :: [NumCol] -> [NumCol] 

Das wirft die Frage auf, ob Ihre Spezifikation tatsächlich das ist, was Sie brauchen. Der Punkt ist, dass das Erkennen eines Tags Ihnen eine Erwartung des Tags dieses Tags gibt. Die Ausgabeart [NumCol] wird der Tatsache nicht gerecht, dass Sie wissen, dass Sie nur die Paare haben.

Wie könnten Sie den Typ Ihrer Funktion verschärfen und trotzdem liefern?

Answer 3

Ein Ansatz besteht darin, DataTypeable und das Data.Data Modul zu verwenden. Dieser Ansatz beruht auf zwei automatisch generierten Typklasseninstanzen, die Metadaten über den Typ für Sie enthalten: Typeable und Data. Sie können sie mit {-# LANGUAGE DeriveDataTypeable #-} ableiten:

data NumCol = Empty | 
      Single Int | 
      Pair Int Int | 
      Lots [Int] deriving (Typeable, Data) 

Jetzt haben wir eine toConstr Funktion, die einen Wert gegeben, uns eine Darstellung ihres Baumeisters gibt:

toConstr :: Data a => a -> Constr 

Dies macht es leicht zu compare two terms nur durch ihre Konstruktoren. Das einzige verbleibende Problem ist, dass wir einen Wert brauchen, um zu vergleichen, wenn wir unser Prädikat definieren! Wir können immer schaffen nur einen Dummy-Wert mit undefined, aber das ist ein bisschen hässlich:

is_pair x = toConstr x == toConstr (Pair undefined undefined) 

Also das letzte, was wir tun müssen, ist eine handliche kleine Klasse definieren, die diese automatisiert. Die Grundidee besteht darin, toConstr auf Nicht-Funktionswerte zu rufen und auf irgendwelche Funktionen zurückzugreifen, indem zuerst undefined übergeben wird.

class Constrable a where 
    constr :: a -> Constr 

instance Data a => Constrable a where 
    constr = toConstr 

instance Constrable a => Constrable (b -> a) where 
    constr f = constr (f undefined) 

Dies beruht auf FlexibleInstance, OverlappingInstances und UndecidableInstances, so ist es vielleicht ein bisschen böse sein, aber unter Verwendung des (in) berühmten Augapfel Satz, sollte es in Ordnung sein. Es sei denn, Sie fügen weitere Instanzen hinzu oder versuchen, sie mit etwas zu verwenden, das kein Konstruktor ist. Dann könnte es explodieren. Heftig. Keine Zusagen.

(=|=) :: (Data a, Constrable b) => a -> b -> Bool 
e =|= c = toConstr e == constr c 

(Der =|= Operator ist ein bisschen ein mnemonic, weil Konstrukteure syntaktisch mit einem | definiert sind:

schließlich mit dem Bösen ordentlich enthalten sind, können wir einen „gleich von Konstruktor“ Operator schreiben.)

Jetzt können Sie fast genau schreiben, was Sie wollten!

filter (=|= Pair) 

Vielleicht möchten Sie auch die Monomorphie-Einschränkung deaktivieren.In der Tat, hier ist die Liste der Erweiterungen, die ich aktiviert habe, dass Sie einfach verwenden können:

Ja, es ist eine Menge. Aber das möchte ich für die Sache opfern. Nicht extra schreiben undefined s.

Ehrlich gesagt, wenn es Ihnen nichts ausmacht lens (aber Junge ist diese Abhängigkeit ein doozy), sollten Sie nur mit dem Prisma Ansatz gehen. Das einzige, was ich empfehlen kann ist, dass Sie die amüsant benannte Data.Data.Data Klasse verwenden.