Abstracte Rekenmachine

Het doel van deze opgave is het implementeren van een bibliotheek voor een rekenmachine die gebruikers toelaat om rekenkundige uitdrukkingen op te bouwen en te manipuleren. Om dit te bereiken, ontwerp je een recursief datatype, Expr, dat in staat is om rekenkundige uitdrukkingen te representeren. Deze uitdrukkingen bestaan uit constante kommagetallen, variabelen en basisrekenkundige operaties (+, *, -, /). Daarnaast implementeer je een reeks functies die fungeren als constructors om op een typeveilige manier uitdrukkingen te creëren en te combineren.

Vereisten

1. Opbouw van uitdrukkingen

Implementeer een datatype Expr. Implementeer vervolgens de volgende primitieve constructors voor het datatype. Het datatype moet Eq implementeren om vergelijking tussen uitdrukkingen mogelijk te maken.

-- | Maak een letterlijke uitdrukking van een zwevendekommagetal.
lit :: Double -> Expr

-- | Maak een variabele uitdrukking van een kleine letter uit het alfabet.
var :: Char -> Expr

Implementeer de volgende functies om op een typeveilige manier uitdrukkingen te combineren.

-- | Negeren van een uitdrukking.
neg :: Expr -> Expr

-- | Maak een optelling van twee deeluitdrukkingen.
add :: Expr -> Expr -> Expr

-- | Maak een aftrekking van twee deeluitdrukkingen.
sub :: Expr -> Expr -> Expr

-- | Maak een vermenigvuldiging van twee deeluitdrukkingen.
mul :: Expr -> Expr -> Expr

-- | Maak een deling van twee deeluitdrukkingen.
div :: Expr -> Expr -> Expr

Stel, we hebben de uitdrukking $2 \times 3$. Dan is het de bedoeling dat we deze uitdrukking als volgt kunnen opbouwen:

mul (lit 2) (lit 3)

Om het lezen van de uitdrukkingen te bevorderen, gebruiken we voornamelijk de infixnotatie.

lit 2 `mul` lit 3

Een andere uitdrukking, $2 \times (-15.5 + x)$, wordt dan:

lit 2 `mul` (lit (-15.5) `add` var 'x')

-- Of zonder infixnotatie:
mul (lit 2) (add (lit (-15.5)) (var 'x'))

De gelijkheidsoperator moet correct werken voor letterlijke waarden en variabelen, maar de evaluatie ervan voor complexere uitdrukkingen wordt niet getest. Je bent vrij om de gelijkheidsoperator naar eigen inzicht te implementeren in deze gevallen.

(lit 1) == (lit 1)
-- Uitvoer: True

(var 'x') == (var 'x')
-- Uitvoer: True

(lit 5) == (lit 6)
-- Uitvoer: False

(var 'x') == (var 'y')
-- Uitvoer: False

2. Variabelen

Implementeer een functie om alle onbekende variabelen in de uitdrukking te verzamelen. De functie moet een alfabetisch gesorteerde lijst van variabelen teruggeven.

-- | Geef een alfabetisch gesorteerde lijst terug van alle variabele karakters in de uitdrukking.
vars :: Expr -> [Char]

Voorbeeld:

vars ((var 'x' `add` (var 'a' `mul` var 'g')))
-- Uitvoer: "agx"

vars ((lit 1 `add` (lit 2 `mul` lit 3)))
-- Uitvoer: ""

3. Evaluatie

Implementeer een functie om uitdrukkingen te evalueren door variabelen te vervangen door hun overeenkomstige uitdrukkingen uit een gegeven mapping, en alle uitdrukkingen zonder onbekenden te berekenen. De functie geeft ofwel een fout (Left EvalError) of een resulterende uitdrukking (Right Expr) terug.

-- | Representatie van mogelijke evaluatiefouten.
data EvalError = Cycle | ZeroDivision

-- | Evalueer een uitdrukking met een lijst van variabele-uitdrukking mappings.
eval :: [(Char, Expr)] -> Expr -> Either EvalError Expr

Variabelen kunnen toegewezen worden aan complexe uitdrukkingen die op hun beurt andere variabelen kunnen bevatten. Deze moeten recursief geëvalueerd worden. Bijvoorbeeld, als we een uitdrukking x * y hebben, en we evalueren met x = 3 en y = x + 1, dan moet het resultaat 12 zijn.

Het evaluatieproces moet twee soorten fouten detecteren:

1. Een ZeroDivision-fout wordt teruggegeven wanneer een deling door nul wordt geprobeerd.
2. Een Cycle-fout wordt teruggegeven wanneer een cyclus wordt gedetecteerd in de variabelenmappings. Een cyclus wordt gedetecteerd wanneer een variabele direct of indirect van zichzelf afhangt. Bijvoorbeeld, als we een uitdrukking x + 3 hebben en we evalueren met x = y + 1 en y = x - 1, dan moet het resultaat een Cycle-fout zijn.

De functie eval houdt geen variabelen bij tussen oproepen. Elke oproep moet onafhankelijk zijn van vorige oproepen.

Wanneer er geen onbekenden meer in de uitdrukking zitten, moet eval ofwel een letterlijke uitdrukking of een fout teruggeven.

Voorbeelden:

eval [('x', lit 3), ('y', lit 4)] (var 'x' `add` var 'y')
-- Uitvoer: Right (lit 7)

eval [('x', var 'x')] (var 'x')
-- Uitvoer: Left Cycle

4. Opmaak

Implementeer een functie om een uitdrukking om te zetten naar een leesbare tekstweergave. Vermijd het gebruik van onnodige haakjes om de uitvoer zo eenvoudig mogelijk te houden. Je mag de uitdrukking herstructureren indien nodig, maar u mag geen getallen of variabelen wijzigen.

-- | Converteer een uitdrukking naar een leesbare string.
prettyPrint :: Expr -> String

Voorbeelden:

prettyPrint (lit 2 `mul` (var 'x' `add` lit 3))
-- Ex. Uitvoer: "2.0 * (x + 3.0)"

prettyPrint (lit 1 `add` lit 2)
-- Ex. Uitvoer: "1.0 + 2.0"

prettyPrint (lit 1 `add` (lit 2 `sub` (lit 3 `add` (lit 4))))
-- Ex. Uitvoer: "1.0 + 2.0 - (3.0 + 4.0)"

prettyPrint (((lit 1 `add` (lit 2 `add` (neg (lit 3)))) `mul` ((neg (lit 4)) `add` (var 'y'))) `sub` (neg (lit 5)))
-- Ex. Uitvoer: "(1.0 + 2.0 - 3.0) * (y - 4.0) + 5.0"

Hierbij gelden de volgende regels:

1. Gebruik de standaard symbolen voor operaties: +, -, *, /, (, ).
2. Volg de gebruikelijke prioriteitsregels van operaties.
3. Gebruik spaties tussen operatoren en hun operanden.
4. Je mag geen getallen of variabelen elimineren of wijzigen, maar je mag hun teken aanpassen.
5. Je mag de volgorde van operaties, getallen en variabelen aanpassen zolang de uitdrukking wiskundig equivalent blijft.
6. Indien de uitdrukkingen niet wiskundig equivalent zijn, krijg je geen punten voor de opmaak.

Indienen

Zorg ervoor dat volgende bestanden in de root van jouw repository staan: Calculator.hs en REPORT.md.

• Calculator.hs bevat de vereiste datatypes en functies uit alle delen van de opgave.
• REPORT.md bevat een korte uitleg over de implementatie en de gemaakte keuzes. Indien bepaalde onderdelen niet volledig geïmplementeerd zijn, leg dan uit welke moeilijkheden je bent tegengekomen en wat je geprobeerd hebt om ze op te lossen. Geef ook aan hoe lang er aan de opgave en deelvragen is gewerkt.

Voeg ook je naam, voornaam en studentennummer toe aan REPORT.md! Anders kan de opgave niet worden geëvalueerd.

Zorg ervoor dat alle vereiste functies correct worden geëxporteerd en automatisch in scope zijn wanneer het bestand wordt geladen in ghci:

ghci Calculator.hs

Alle voorbeelden uit de opgave moeten zonder fouten werken wanneer ze in ghci worden uitgevoerd.

Evaluatie

Je wordt verwacht deze opgave individueel te maken. Hierbij is het gebruik van generative AI om (delen van) de code te schrijven niet toegelaten.

Deze opgave wordt beoordeeld op correctheid, codekwaliteit, en een mondelinge toelichting. We starten met 0 punten, en er kunnen maximaal 10 punten verdiend worden:

• Correctheid draagt bij tot de punten.
• Een gebrek aan codekwaliteit kost punten. Je kan nooit meer dan 3 punten verliezen op codekwaliteit.
• In de mondelinge toelichting moet je kort de werking van je eigen code toelichten waarbij er vanuit het onderwijsteam ook vragen gesteld worden. Je toont hierdoor aan dat je de ingediende code zelf geschreven hebt en dus beheerst. Indien je dit niet overtuigend kan doen, en er hierdoor dus twijfel ontstaat of je de code zelf geschreven hebt, wordt dit als een vorm van plagiaat beschouwd en conform het examenreglement aan de examencommissie gerapporteerd. De examencommissie beslist over de verdere afhandeling en sancties.

Correctheid (max. 10 punten)

De implementatie moet correct werken zoals beschreven in de specificatie.

• Opbouw van uitdrukkingen (lit, var, neg, add, sub, mul, div): 1 punt te verdienen
• Oplijsten van variabelen (vars): 1 punt te verdienen
• Evalueren van uitdrukkingen (eval): 5 punten te verdienen
  • Correcte evaluatie: 3 punten te verdienen
    • Correcte evaluatie van uitdrukkingen zonder onbekenden: 1 punt
    • Correcte evaluatie van uitdrukkingen met onbekenden, waarbij alle onbekenden worden meegegeven: 2 punten
    • Correcte evaluatie van uitdrukkingen waarbij onbekenden worden meegegeven in meerdere stappen: 3 punten
  • Correcte detectie van cycli: 1 punt te verdienen
  • Correcte detectie van deling door nul: 1 punt te verdienen
• Opmaak van uitdrukkingen (prettyPrint): 3 punten te verdienen
  • Basisopmaak, zonder vereenvoudiging: 1 punt
  • Aanzienelijke vereenvoudiging van uitdrukkingen: 2 punten
  • Vereenvoudiging van uitdrukkingen op hetzelfde niveau als de voorbeelden: 3 punten

Codekwaliteit (max. 3 minpunten)

Om een maximaal aantal punten te behalen, moet de code goed gestructureerd zijn, en gebruik maken van goede programmeerpraktijken. Schrijf steeds type signatures bij functies. Werk op een functionele manier, en schrijf duidelijke, beknopte, en becommentarieerde code.

Aspect	Beschrijving
0 minpunten	De code is zeer duidelijk, goed gestructureerd en functioneel.
1 minpunt	Kleine problemen met structuur, maar zonder grote impact op de leesbaarheid. Mogelijk wat overbodige of imperatieve code.
2 minpunten	De code is moeilijk leesbaar, bevat veel onnodige complexiteit of volgt geen functionele stijl.
3 minpunten	De code is onleesbaar, chaotisch of bevat ernstige structurele fouten.

Het gebruik van alle standaard Haskell-modules is toegestaan.