Menu schließen

Haskell: Implementierung α- und β-Konversion Lam..

Frage: Haskell: Implementierung α- und β-Konversion Lam..
(keine Antwort)


Autor
Beiträge 1
0
Gegeben sei ein algebraischer Datentyp LExpr zur Darstellung von Ausdrücken
des λ-Kalküls ohne Konstanten.

data LExpr = Var String -- Variable
| App LExpr LExpr -- Funktionsapplikation
| Lam String LExpr -- Lambda-Abstraktion
deriving (Eq, Show)

Mit diesem lassen sich λ-Ausdrücke in Haskell darstellen.

1.
Schreiben Sie eine Funktion

free :: LExpr -> [String]

welche die freien Vorkommen von Variablen eines Ausdrucks berechnet.

free :: LExpr ->[String]
free (Var x) = [x]
free (App e e`) = free e ++ free e`
free (Lam x e) = filter (/= x) $ free e

2. Schreiben Sie nun eine Funktion

bound :: LExpr ->[String]

welche die gebundenen Vorkommen von Variablen eines Ausdrucks berechnet.

bound :: LExpr ->[String]
bound (Var x) =[]
bound (App e e`) = bound e ++ bound e`
bound (Lam x e) = (filter (== x) $ variables e) ++ bound e
where variables (Var x) =[x]
variables (Lam x e) = variables e
variables (App e e`) = variables e ++ variables e`

3. Um α -Konversion durchführen zu können, müssen neue Variablennamen eingeführt werden.

Schreiben Sie dazu eine Funktion

newVar :: [String] -> String

die eine Liste von nicht erlaubten Variablennamen als Parameter nimmt und einen neuen Variablennamen zurückgibt, der unterschiedlich zu allen gegebenen Namen ist.

4. Schreiben Sie nun unter Verwendung von newVar eine Funktion

subst :: LExpr -> String -> LExpr -> LExpr

sodass subst m x e die Substitution e [ x ← m ] implementiert

Ich habe Probleme beim Implementieren der Funktionen newVar und subst.
Kann mir vielleicht jemand hier im Forum helfen?
Frage von Haskell98 | am 13.01.2021 - 11:04





Leider noch keine Antworten vorhanden!


Verstoß melden Antworten
Hast Du eine eigene Frage an unsere Informatik-Experten?

4 ähnliche Fragen im Forum: 0 passende Dokumente zum Thema:
> Du befindest dich hier: Support-Forum - Informatik
ÄHNLICHE FRAGEN:
  • Optimierung der Java-Implementierung
    Hallo Leute! Ich habe eine Hauaufgabe im Fach Informatik bekommen. Ich habe alle Aufgaben gemacht außer einer Aufgabe. Sie ..
  • Haskell
    Eine Zahl soll in einen Buchstaben geändert werden. z.B. toChar 10 --> `K` (Quelle: http://www.pns-berlin.de/skripte.html) ..
  • Algebraische Datentypen : Mengen
    (Haskell) Implementieren Sie die Funktion vonListe :: Eq a => -> Menge a die aus einer Liste vom Typ a eine Menge ..
  • Haskell uhrzeit
    Wir führen den Datentypen type Zeit = (Int,Int) ein, der eine Uhrzeit als Paar (h,m) von Stunden- und Minutenwert darstellt (h..
  • mehr ...