Typ familj
Inom datavetenskap associerar en typfamilj datatyper med andra datatyper , med hjälp av en funktion på typnivå definierad av en öppen samling av giltiga instanser av indatatyper och motsvarande utdatatyper.
Typfamiljer är en funktion i vissa typsystem som tillåter att delfunktioner mellan typer definieras genom mönstermatchning . Detta till skillnad från datatypskonstruktörer , som definierar injektiva funktioner från alla typer av en viss typ till en ny uppsättning typer, och typsynonymer (aka typedef ), som definierar funktioner från alla typer av en viss typ till en annan befintlig uppsättning av typer med ett enda fall.
Typfamiljer och typklasser är nära besläktade: normaltypklasser definierar delfunktioner från typer till en samling namngivna värden genom mönstermatchning på indatatyperna, medan typfamiljer definierar partiella funktioner från typer till typer genom mönstermatchning på indatatyperna. Faktum är att i många användningar av typfamiljer finns det en enda typklass som logiskt innehåller både värden och typer som är associerade med varje instans. En typfamilj som deklareras i en typklass kallas en associerad typ .
Programmeringsspråk med stöd för typfamiljer eller liknande funktioner inkluderar Haskell (med en gemensam språktillägg), Standard ML (genom dess modulsystem), Scala (under namnet "abstrakta typer") och C++ (genom användning av typedefs i mallar) .
Variationer
TypeFamilies i Glasgow Haskell-kompilatorn stöder både typsynonymfamiljer och datafamiljer . Typsynonymfamiljer är den mer flexibla (men svårare att typkontrollera) formen, vilket tillåter att typerna i typfunktionens koddomän är vilken typ som helst med lämplig typ . Datafamiljer, å andra sidan, begränsar koddomänen genom att kräva att varje instans definierar en ny typkonstruktor för funktionens resultat. Detta säkerställer att funktionen är injektiv , vilket gör att klienternas sammanhang kan dekonstruera typfamiljen och få den ursprungliga argumenttypen.
Motivation och exempel
Typfamiljer är användbara för att abstrahera mönster där en gemensam "organisation" eller "struktur" av typer upprepas, men med olika specifika typer i varje fall. Typiska användningsfall inkluderar att beskriva abstrakta datatyper som generiska samlingar eller designmönster som modell–vy–kontroller .
Självoptimerande abstrakta datatyper
En av de ursprungliga motiven för introduktionen av associerade typer var att tillåta abstrakta datatyper att parametriseras efter deras innehållstyp så att datastrukturen som implementerar den abstrakta typen varierar på ett "självoptimerande" sätt. Normala algebraiska datatypparametrar kan bara beskriva datastrukturer som beter sig enhetligt med avseende på alla argumenttyper. Associerade typer kan dock beskriva en familj av datastrukturer som har ett enhetligt gränssnitt men varierar i implementering enligt en eller flera typparametrar. Till exempel, med hjälp av Haskells associerade typer notation, kan vi deklarera en typklass av giltiga arrayelementtyper , med en associerad datafamilj som representerar en array av den elementtypen:
klass ArrayElem e där data Array e index :: Array e -> Int -> e
Förekomster kan sedan definieras för denna klass, som definierar både datastrukturen som används och operationerna på datastrukturen på en enda plats. För effektivitet kan vi använda en vektorrepresentation med packade bitar för arrayer av booleska värden, medan vi använder en normal arraydatastruktur för heltalsvärden. Datastrukturen för arrayer av ordnade par definieras rekursivt som ett par arrayer av var och en av elementtyperna.
instans ArrayElem Bool där data Array Bool = BoolArray BitVector index ( BoolArray ar ) i = indexBitVector ar i instans ArrayElem Int där data Array Int = IntArray UIntArr index ( IntArray ar ) i = indexUIntArr ar i instans ( ArrayElem a instans , Array> Elem a ) ArrayElem ( a , b ) där data Array ( a , b ) = PairArray ( Array a ) ( Array b ) index ( PairArray ar br ) = ( index ar i , index br i )
Med dessa definitioner, när en klient refererar till en Array (Int, Bool) väljs en implementering automatiskt med de definierade instanserna.
En klass för samlingar
Om vi inverterar det föregående exemplet kan vi också använda typfamiljer för att definiera en klass för samlingstyper, där typfunktionen mappar varje samlingstyp till dess motsvarande elementtyp:
klass Samlar c där typ Elem c tom :: c infoga :: Elem c -> c -> c toList :: c -> [ Elem c ] instans Samlar [ e ] där typ Elem [ e ] = e tom = [] infoga = ( : ) toList = id instans Ord e => Samlar ( Set . Set e ) där typ Elem ( Set . Set e ) = e tom = Set . tom infoga = Set . insert toList = Set . att lista
I det här exemplet är användningen av en typsynonymfamilj i stället för en datafamilj viktig, eftersom flera samlingstyper kan ha samma elementtyp.
Jämförelse med funktionella beroenden
Funktionella beroenden är en annan typ av systemfunktion som har liknande användningsområden som associerade typer. Medan en associerad typ lägger till en namngiven typfunktion som mappar den omslutande typklassens parametrar till en annan typ, listar ett funktionellt beroende resultattypen som en annan parameter av typklassen och lägger till en begränsning mellan typparametrarna (t.ex. "parameter a bestämmer unikt parameter b ", skrivet a -> b ). De vanligaste användningarna av funktionella beroenden kan direkt konverteras till associerade typer och vice versa.
Typfamiljer anses generellt vara lättare att typkontrollera än funktionella beroenden. En annan fördel med associerade typer framför funktionella beroenden är att de senare kräver att klienter som använder typklassen anger alla beroende typer i sina sammanhang, inklusive de som de inte använder; eftersom associerade typer inte kräver detta kräver att lägga till en annan associerad typ till klassen att endast klassens instanser uppdateras, medan klienter kan förbli oförändrade. De huvudsakliga fördelarna med funktionella beroenden jämfört med typfamiljer är deras ökade flexibilitet vid hantering av några ovanliga fall.