Vraag Wanneer moeten constructeurs van een gegevenstype worden blootgesteld bij het ontwerpen van gegevensstructuren?


Bij het ontwerpen van datastructuren in functionele talen zijn er 2 opties:

  1. Ontmasker hun constructeurs en patroon match op hen.
  2. Verberg hun constructors en gebruik hogere functies om de datastructuren te onderzoeken.

In welke gevallen, wat is gepast?

Patroonaanpassing kan code veel leesbaarder of eenvoudiger maken. Aan de andere kant, als we iets in de definitie van een gegevenstype moeten veranderen, moeten alle plaatsen waar we patroon-overeenkomst op hen hebben (of ze construeren) worden bijgewerkt.


Ik heb deze vraag al een tijdje zelf gesteld. Vaak overkomt het mij dat ik begin met een eenvoudige datastructuur (of zelfs een type alias) en het lijkt erop dat constructeurs + patroonaanpassing de gemakkelijkste aanpak zijn en een schone en leesbare code produceren. Maar later worden dingen gecompliceerder, ik moet de gegevenstype-definitie veranderen en een groot deel van de code refactoren.


11
2017-09-06 14:59


oorsprong


antwoorden:


Als het type wordt gebruikt om waarden weer te geven met een canonieke definitie en representatie (veel wiskundige objecten vallen onder deze categorie), en het is niet mogelijk om "ongeldige" waarden te construeren met behulp van het type, dan zou u de constructeurs moeten blootstellen.

Als u bijvoorbeeld twee tweedimensionale punten vertegenwoordigt met uw eigen type (inclusief een nieuw type), kunt u net zo goed de constructor blootleggen. De realiteit is dat een verandering in dit datatype geen verandering zal zijn in hoe 2d punten worden weergegeven, het zal een verandering zijn in je behoefte om 2d punten te gebruiken (misschien generaliseer je naar 3d ruimte, misschien ben je een concept van lagen toevoegen, of wat dan ook), en is bijna zeker aandacht nodig in de delen van de code met behulp van waarden van dit type, ongeacht wat je doet. [1]

Een complex type dat iets specifieks voor uw toepassing of veld vertegenwoordigt, is vrij waarschijnlijk onderhevig aan wijzigingen in de weergave terwijl het soortgelijke activiteiten blijft ondersteunen. Daarom wilt u alleen andere modules, afhankelijk van de bewerkingen, niet van de interne structuur. Dus je moet de constructeurs niet blootstellen.

Andere typen vertegenwoordigen dingen met canonieke definities, maar niet canonieke representaties. Iedereen kent het eigenschappen verwacht van kaarten en sets, maar er zijn veel verschillende manieren om waarden weer te geven die die eigenschappen ondersteunen. Dus je wilt opnieuw alleen andere modules, afhankelijk van de bewerkingen die ze ondersteunen, niet van de specifieke representaties.

Sommige typen, al dan niet eenvoudig, met canonieke representaties, maken de constructie mogelijk van waarden in het programma die geen geldige waarde vertegenwoordigen in het abstracte concept dat het type verondersteld wordt weer te geven. Een eenvoudig voorbeeld zou een type zijn dat een zelfbalancerende binaire zoekboom vertegenwoordigt; clientcode met toegang tot de constructors kan gemakkelijk ongeldige bomen construeren. Als u de constructeurs blootstelt, betekent dit dat u moet aannemen dat dergelijke waarden die van buiten worden doorgegeven ongeldig zijn en dat u daarom iets zinnigs moet doen, zelfs voor bizarre waarden, of dat het de verantwoordelijkheid is van de programmeurs die met uw interface werken om ervoor te zorgen ze overtreed geen aannames. Het is meestal beter om te voorkomen dat dergelijke typen direct buiten uw module worden gebouwd.

Eigenlijk komt het neer op het concept dat je type hoort voor te stellen. Als uw concept op een zeer eenvoudige en voor de hand liggende manier [2] rechtstreeks naar waarden in een gegevenstype wijst die niet "meer inclusief" zijn dan het concept omdat de compiler de benodigde invarianten niet kan controleren, dan is het concept vrij veel " hetzelfde "als het gegevenstype en het blootstellen van de structuur is prima. Zo niet, dan moet je de structuur waarschijnlijk verborgen houden.


[1] Een waarschijnlijke verandering is echter om het numerieke type dat u gebruikt voor de coördinaatwaarden te wijzigen, dus u moet waarschijnlijk nadenken over het minimaliseren van de impact van dergelijke wijzigingen. Dat is behoorlijk orthogonaal aan het feit of je de constructeurs al dan niet blootstelt.

[2] "Duidelijk" hier, wat betekent dat als je 10 mensen onafhankelijk zou vragen om een ​​gegevenstype te bedenken dat het concept vertegenwoordigt, ze allemaal met hetzelfde terugkomen, modulo de namen veranderen.


2
2017-09-07 01:40



De essentiële factor voor mij is het antwoord op de volgende vraag:

Is de structuur van mijn datatype relevant voor de buitenwereld?

De interne structuur van het lijst-datatype is bijvoorbeeld zeer relevant voor de buitenwereld - het heeft een inductieve structuur die zeker zeer nuttig is om aan consumenten bloot te leggen, omdat ze functies construeren die voortkomen uit inductie van de structuur van de lijst. Als de lijst eindig is, worden deze functies gegarandeerd beëindigd. Het op deze manier definiëren van functies maakt het gemakkelijk om eigenschappen over hen te bieden, opnieuw door inductie.

Daarentegen is het het beste voor de Set datatype dat abstract moet worden gehouden. Intern wordt het geïmplementeerd als een boom in de containers pakket. Het had echter net zo goed geïmplementeerd kunnen zijn met arrays, of (nuttiger in een functionele setting) met een boom met een iets andere structuur en met respect voor verschillende invarianten (gebalanceerde of ongebalanceerde vertakkingsfactoren, enz.). De noodzaak om eventuele invarianten boven en boven die uit te drukken die de constructeurs al via hun typen afdwingen, sluit overigens uit dat het datatype concreet moet zijn.

Het essentiële verschil tussen het lijstvoorbeeld en het ingestelde voorbeeld is dat het Set datatype is enkel en alleen relevant voor de operaties die mogelijk zijn op Set'S. Terwijl lijsten relevant zijn omdat de standaardbibliotheek al veel functies biedt om daarop in te spelen, maar ook hun structuur is relevant.

Als een sidenote kan men bezwaar maken dat eigenlijk de inductieve structuur van lijsten, die zo fundamenteel is om functies te schrijven waarvan de beëindiging en het gedrag gemakkelijk te redeneren zijn, abstract gevangen wordt door twee functies die lijsten gebruiken: foldr en foldl. Gezien deze twee basislijstoperators, hoeven de meeste functies de structuur van een lijst helemaal niet te inspecteren, en dus zou kunnen worden gesteld dat lijsten te eenvoudig moeten worden gehouden. Dit argument generaliseert naar vele andere vergelijkbare structuren, zoals alle Traversablestructuren, allemaal Foldable structuren, enz. Het is echter vrijwel onmogelijk om alle mogelijke recursiepatronen op lijsten vast te leggen, en in feite zijn veel functies helemaal niet recursief. Alleen gegeven foldr en foldlzou men schrijven head bijvoorbeeld zou nog steeds mogelijk zijn, hoewel vrij vervelend:

head xs = fromJust $ foldl (\b x -> maybe (Just x) Just b) Nothing xs

We zijn veel beter af als we de interne structuur van de lijst weggeven.

Een laatste punt is dat de werkelijke weergave van een datatype soms niet relevant is voor de buitenwereld, omdat het een soort van geoptimaliseerd is en misschien niet de canonieke weergave is, of er is geen enkele "canonieke" representatie. In deze gevallen wilt u uw datatype abstract houden, maar wel "weergaven" van uw datatype aanbieden, die wel concrete weergaven bieden waarop patroonafstemming kan worden toegepast.

Een voorbeeld zou zijn als u een a wilt definiëren Complex datatype van complexe getallen, waarbij zowel cartesiaanse vormen als polaire vormen als canoniek kunnen worden beschouwd. In dit geval zou je het houden Complex abstract, maar exporteer twee views, dwz functies polar en cartesian die een paar van een lengte en een hoek of een coördinaat retourneren in respectievelijk het cartesische vlak.


10
2017-09-06 15:37



Welnu, de regel is vrij eenvoudig: als het gemakkelijk is om verkeerde waarden te construeren door de feitelijke constructors te gebruiken, laat ze dan niet direct worden gebruikt, maar geef in plaats daarvan slimme constructeurs. Dit is het pad gevolgd door enkele datastructuren zoals Map en Set, die gemakkelijk fout kunnen gaan.

Dan zijn er de types waarvoor het onmogelijk of moeilijk is om inconsistente / verkeerde waarden te construeren, ofwel omdat het type dat helemaal niet toestaat of omdat je bottoms zou moeten introduceren. Het lengte-geïndexeerde lijsttype (gewoonlijk genoemd Vec) en de meeste monaden zijn daar voorbeelden van.

Uiteindelijk is dit je eigen beslissing. Verplaats uzelf naar het perspectief van de gebruiker en maak de afweging tussen gemak en veiligheid. Als er geen afweging is, stel dan altijd de constructeurs bloot. Anders zullen uw bibliotheekgebruikers u haten vanwege de onnodige dekking.


7
2017-09-06 15:30



Als het gegevenstype een eenvoudig doel dient (zoals Maybe a) en er kunnen geen (expliciete of impliciete) aannames over het gegevenstype worden geschonden door direct het construeren van een waarde via de gegevensconstructors, zou ik de constructeurs blootstellen.

Aan de andere kant, als het gegevenstype complexer is (zoals een gebalanceerde boom) en / of de interne weergave waarschijnlijk zal veranderen, verberg ik meestal de constructeurs. Wanneer u een pakket gebruikt, is er een ongeschreven regel die de interface die wordt weergegeven door een niet-interne module 'veilig' moet zijn om te gebruiken voor het gegeven gegevenstype. Gezien het gebalanceerde tree-voorbeeld, stelt het blootstellen van de data-constructors u in staat om (per ongeluk) een ongebalanceerde boom te construeren, zodat de veronderstelde runtime-garanties voor het doorzoeken van de boom enz. Kunnen worden geschonden.


5
2017-09-06 15:26



Ik zou een andere, merkbaar meer beperkende regel voorstellen dan de meeste mensen. Het centrale criterium zou zijn:

Garandeert u dat dit type nooit zal veranderen? Als dat zo is, is het misschien een goed idee om de constructeurs bloot te leggen. Veel succes daarmee!

Maar de typen waarvoor u die garantie kunt maken, zijn over het algemeen heel eenvoudige, generieke "foundation" -typen zoals Maybe, Either of [], welke je misschien wel eens zou kunnen schrijven en dan nooit meer opnieuw zult bezoeken.

Hoewel zelfs die kunnen worden ondervraagd, omdat ze van tijd tot tijd worden herzien; er zijn mensen die Church-gecodeerde versies van hebben gebruikt Maybe en List in verschillende contexten om uitvoeringsredenen, bijvoorbeeld:

{-# LANGUAGE RankNTypes #-}

newtype Maybe' a = Maybe' { elimMaybe' :: forall r. r -> (a -> r) -> r }
nothing = Maybe' $ \z k -> z
just x = Maybe' $ \z k -> k x

newtype List' a = List' { elimList' :: forall r. (a -> r -> r) -> r -> r }
nil = List' $ \k z -> z
cons x xs = List' $ \k z -> k x (elimList' k z xs)

Deze twee voorbeelden benadrukken iets belangrijks: u kunt de Maybe' type implementatie zoals hierboven getoond bij elke andere implementatie, zolang het de volgende drie functies ondersteunt:

nothing :: Maybe' a
just :: a -> Maybe' a
elimMaybe' :: Maybe' a -> r -> (a -> r) -> r

... en de volgende wetten:

elimMaybe' nothing z x  == z
elimMaybe' (just x) z f == f x

En deze techniek kan worden toegepast op elk algebraïsch gegevenstype. Wat voor mij zegt dat patroonafstemming met betonconstructeurs net onvoldoende abstract is; het levert je niet echt iets op dat je niet uit het abstracte constructeurs + destructorpatroon kunt halen, en het verliest aan implementatieflexibiliteit.


1
2017-09-07 17:44