Haskell < Haskell < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:29 Sa 05.11.2005 | | Autor: | Bastiane |
Hallo!
Nun mal wieder eine Haskell-Aufgabe:
Folgender Datentyp für reguläre Ausdrücke wird definiert:
data Reg = Eps | Sym Char | Cat Reg Reg | Alt Reg Reg
deriving (Show)
Und nun soll ich eine Funktion
language :: Reg -> [String]
schreiben, die die Sprache berechnet, die durch einen regulären Ausdruck bezeichnet wird. Beispiel:
language abc
=> ["a","b","c"]
Ich habe bereits geschrieben:
language Eps = [""]
language (Sym zeichen) = [ [zeichen] ]
(ich muss das [ [zeichen] ] hier so komisch schreiben, da es sonst als Link auf die Mathebank gewertet wird... Also die Leerzeichen dazwischen gehören da natürlich nicht hin...)
Das stimmt doch so weit, oder?
Nun habe ich es mit
language (Cat a b)
versucht, allerdings bekomme ich das nicht hin. Prinzip ist doch, dass ich zu jedem Element der Sprache von a jedes Element der Sprache von b dahinterschalten muss. Aber das ist ja nicht einfach eine Verknüpfung von Listen, sondern das muss ja quasi ein Element werden.
Beispiel: die Sprache von digit 'Cat' digit soll sein: ["00","01","02",...,"09","10","11",...,"19",...,"90",...,"99"]. Wenn ich aber einfach nur eine Listenkonkatenation mache, käme da bestenfalls das hier raus: ["0","0","0","1","0","2",...] oder so etwas ähnliches. Mein Problem ist also, wie ich zwei Listenelemente zu einem zusammenschreibe. Ist mein Problem verständlich? Oder muss ich das für diese Aufgabe sowieso ganz anders machen?
So, und dann noch zum letzten Fall:
language (Alt a b) = (language a) ++ (language (b)
Ich dachte, das könnte eigentlich so hinhauen, aber ich bekomme immer eine Fehlermeldung, die ich nicht verstehe, denn es soll wohl ein Semikolon zu viel sein, nur hier steht ja gar kein Semikolon... Also muss da wohl irgendwas anderes falsch sein...
Wäre schön, wenn mir hier jemand helfen könnte.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:47 So 06.11.2005 | | Autor: | Frank05 |
> Folgender Datentyp für reguläre Ausdrücke wird definiert:
>
> data Reg = Eps | Sym Char | Cat Reg Reg | Alt Reg Reg deriving (Show)
Wie soll der reguläre Ausdrücke darstellen können ohne einen Kleene-Operator? Mit diesem Datentyp bekommst du nur endliche Sprachen und damit nur eine klitzekleine Teilmenge der reg. Sprachen. Ich nehm mal an die Erweiterung kommt nächste Woche 
> Und nun soll ich eine Funktion
>
> language :: Reg -> [String]
>
> schreiben, die die Sprache berechnet, die durch einen
> regulären Ausdruck bezeichnet wird. Beispiel:
> language abc
> => ["a","b","c"]
Was ist abc? Wenn das eine Variable ist, die du vorher definiert hast wärs nicht schlecht, wenn du die Definition angeben würdest. Wenn es nicht vom Typ Reg ist macht das Beispiel nämlich keinen Sinn.
> Ich habe bereits geschrieben:
>
> language Eps = [""]
Ok.
> language (Sym zeichen) = [ [zeichen] ]
>
> (ich muss das [ [zeichen] ] hier so komisch schreiben, da
> es sonst als Link auf die Mathebank gewertet wird... Also
> die Leerzeichen dazwischen gehören da natürlich nicht
> hin...)
Kein Grund zur Panik. Du kannst auch links 2 und rechts 3 Leerzeichen machen.. das interessiert niemanden und den Compiler schon dreimal nicht.
> Das stimmt doch so weit, oder?
Ja sieht gut aus soweit.
> Nun habe ich es mit
>
> language (Cat a b)
>
> versucht, allerdings bekomme ich das nicht hin. Prinzip ist
> doch, dass ich zu jedem Element der Sprache von a jedes
> Element der Sprache von b dahinterschalten muss. Aber das
> ist ja nicht einfach eine Verknüpfung von Listen, sondern
> das muss ja quasi ein Element werden.
> Beispiel: die Sprache von digit 'Cat' digit soll sein:
> ["00","01","02",...,"09","10","11",...,"19",...,"90",...,"99"].
Wenn digit entsprechend definiert wurde ja.
> Wenn ich aber einfach nur eine Listenkonkatenation mache,
> käme da bestenfalls das hier raus:
> ["0","0","0","1","0","2",...] oder so etwas ähnliches. Mein
> Problem ist also, wie ich zwei Listenelemente zu einem
> zusammenschreibe. Ist mein Problem verständlich? Oder muss
> ich das für diese Aufgabe sowieso ganz anders machen?
Die Idee ist richtig und wenn es dir zu komplex wird, dann hilft es, wenn man das Ganze einfach mit Hilfe zusätzlicher Funktionen in überschaubarere Teile zerlegt. Was du bei Cat machen willst ist ja im Prinzip ein Kreuzprodukt der beiden Listen, also fangen wir mal an mit:
language (Cat a b) = cross (language a) (language b)
Und jetzt überlegen wir uns noch wie cross aussehen muss. Zuerst die Typisierung:
cross :: [String] -> [String] -> [String]
Und jetzt machen wir genau das, was du oben schon selbst gesagt hast: Jedes Element aus der ersten Liste nehmen und etwas damit machen:
cross (x:xs)
gibt uns schonmal mit x die Elemente der ersten Liste. Und was machen wir mit denen? Wir hängen sie vorne an jedes Element der zweiten Liste:
cross (x:xs) ys = (vorne x ys)
Diese Aufgabe können wir wieder an eine weitere Hilfsfunktion delegieren. Und zum Schluss müssen alle so entstandenen Ergebnisse wieder in eine Liste gefasst werden:
cross (x:xs) ys = (vorne x ys) ++ cross xs ys
und den Terminierungsfall noch:
cross _ _ = []
Bleibt also noch das Vorne-Anhängen:
vorne :: String -> [String] -> [String]
vorne x (y:ys) = (x++y) : (vorne x ys)
vorne x [] = []
Wenn du etwas fitter wirst in Haskell kannst du diese zusätzlichen Hilfsfunktionen zunehmend vermeiden, aber zu Beginn ist es so leichter die Aufgabe in kleineren Teilproblemen zu lösen. Du hättest z.B. cross auch so definieren können:
cross (x:xs) ys = [ x++y | y <- ys ] ++ cross xs ys
(Aber im Prinzip passiert da genau das Gleiche)
> So, und dann noch zum letzten Fall:
>
> language (Alt a b) = (language a) ++ (language (b)
Sieht gut aus so, wenn da nicht die Klammer vor dem b wäre (ich nehm an ein Tippfehler?)
> Ich dachte, das könnte eigentlich so hinhauen, aber ich
> bekomme immer eine Fehlermeldung, die ich nicht verstehe,
> denn es soll wohl ein Semikolon zu viel sein, nur hier
> steht ja gar kein Semikolon... Also muss da wohl irgendwas
> anderes falsch sein...
Vielleicht doch kein Tippfehler 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:06 So 06.11.2005 | | Autor: | Bastiane |
Hallo Frank!
Schon mal vielen Dank für die superschnelle Antwort. ![[sunny]](/images/smileys/sunny.gif "[sunny]")
> > Folgender Datentyp für reguläre Ausdrücke wird definiert:
> >
> > data Reg = Eps | Sym Char | Cat Reg Reg | Alt Reg Reg
> deriving (Show)
>
> Wie soll der reguläre Ausdrücke darstellen können ohne
> einen Kleene-Operator? Mit diesem Datentyp bekommst du nur
> endliche Sprachen und damit nur eine klitzekleine Teilmenge
> der reg. Sprachen. Ich nehm mal an die Erweiterung kommt
> nächste Woche
Naja, das war halt so die Aufgabenstellung. Der Prof will wohl nur endliche reguläre Ausdrücke haben - schließlich sind wir nicht in Info III, wo (ein ganz anderer) Prof bei uns gerade (ich bin dort Tutor...) [mm] \omega-Sprachen [/mm] macht. Naja, also was nächste Woche kommt, sehen wir dann.
> > Und nun soll ich eine Funktion
> >
> > language :: Reg -> [String]
> >
> > schreiben, die die Sprache berechnet, die durch einen
> > regulären Ausdruck bezeichnet wird. Beispiel:
> > language abc
> > => ["a","b","c"]
>
> Was ist abc? Wenn das eine Variable ist, die du vorher
> definiert hast wärs nicht schlecht, wenn du die Definition
> angeben würdest. Wenn es nicht vom Typ Reg ist macht das
> Beispiel nämlich keinen Sinn.
Sorry - irgendwie wollte ich die Frage kurz halten und hab' die Hälfte vergessen... Beispiele für reguläre Ausdrücke sind:
abc = (Sym 'a') 'Alt' (Sym 'b') 'Alt' (Sym 'c')
digit = (Sym '0') 'Alt' (Sym '1') 'Alt' (Sym '2') 'Alt' (Sym '3') 'Alt' (Sym '4') 'Alt'(Sym '5') 'Alt' (Sym '6') 'Alt' (Sym '7') 'Alt' (Sym '8') 'Alt' (Sym '9')
number = digit 'Cat' digit 'Cat' (Eps 'Alt' (Sym '.' 'Cat' digit 'Cat' digit))
Den Rest deine Antwort habe ich gerade mal überflogen (ist jetzt doch schon zu spät, noch weiter zu programmieren...), aber ich denke, dass ich damit auf jeden Fall erstmal weiter komme. Vielen Dank. ![[applaus]](/images/smileys/applaus.gif "[applaus]")
Viele Grüße und ![[gutenacht]](/images/smileys/gutenacht.gif "[gutenacht]")
Bastiane
P.S.:
> > So, und dann noch zum letzten Fall:
> >
> > language (Alt a b) = (language a) ++ (language (b)
>
> Sieht gut aus so, wenn da nicht die Klammer vor dem b wäre (ich nehm an ein Tippfehler?)
Mmh - da kommt aber immer noch dieselbe Fehlermeldung, wenn ich die halbe Klammer weglassen... ![[haee]](/images/smileys/haee.gif "[haee]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:03 Fr 11.11.2005 | | Autor: | Bastiane |
Hallo Frank oder jemand anders!
Also erstmal geht mein Internet zu Hause nicht, deswegen schreibe ich jetzt auch nur recht kurz... (sitze in der Uni...)
Die erste Aufgabe hat mit deiner Hilfe geklappt, obwohl ich noch ein paar Kleinigkeiten verändern musste. Und auch die eine Fehlermeldung kam irgendwann nicht mehr...
Jedenfalls habe ich dann auch noch eine zweite und dritte Aufgabe, und für die dritte fehlt mir irgendwie der Ansatz:
Ich soll eine Funktion schreiben, die überprüft, ob eine Zeichenkette auf einen regulären Ausdruck passt, also ob die Zeichenkette in der von dem regulären Ausdruck bezeichneten Sprache enthalten ist (aber nicht, indem ich das auf "language" zurückführe, sondern effizienter).
Ich habe schon irgendwas geschrieben, wie ich das mache, wenn der reguläre Ausdruck nur aus Eps, aus Sym Char oder aus Alt Reg Reg besteht, aber ich weiß nicht, wie ich das machen soll, wenn er aus Cat Reg Reg besteht. Denn ich kann doch da nicht sagen, dass er entweder in dem ersten oder dem zweiten "Reg" enthalten sein muss, denn durch das Cat wird das ja quasi verbunden. Also kann es sein, dass der Anfang des gesuchten Strings im ersten Reg enthalten ist und das Ende im zweiten, ich weiß nur irgendwie nicht, wie ich das programmieren soll. Denn es kann ja sein, dass nur der erste Buchstabe des Strings im ersten Reg enthalten ist, oder die ersten beiden oder die ersten drei usw. und das kann ich doch nicht alles einzeln schreiben.
Ich hoffe, es ist irgendwie klar geworden, was ich meine - irgendwie bekomme ich das gerade nicht besser formuliert... Evtl. kannst du mir einen Tipp geben - auch erstmal nicht unbedingt direkt auf Haskell bezogen...
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:11 So 13.11.2005 | | Autor: | Frank05 |
> Jedenfalls habe ich dann auch noch eine zweite und dritte
> Aufgabe, und für die dritte fehlt mir irgendwie der
> Ansatz:
>
> Ich soll eine Funktion schreiben, die überprüft, ob eine
> Zeichenkette auf einen regulären Ausdruck passt, also ob
> die Zeichenkette in der von dem regulären Ausdruck
> bezeichneten Sprache enthalten ist (aber nicht, indem ich
> das auf "language" zurückführe, sondern effizienter).
>
> Ich habe schon irgendwas geschrieben, wie ich das mache,
> wenn der reguläre Ausdruck nur aus Eps, aus Sym Char oder
> aus Alt Reg Reg besteht, aber ich weiß nicht, wie ich das
> machen soll, wenn er aus Cat Reg Reg besteht. Denn ich kann
> doch da nicht sagen, dass er entweder in dem ersten oder
> dem zweiten "Reg" enthalten sein muss, denn durch das Cat
> wird das ja quasi verbunden. Also kann es sein, dass der
> Anfang des gesuchten Strings im ersten Reg enthalten ist
> und das Ende im zweiten, ich weiß nur irgendwie nicht, wie
> ich das programmieren soll. Denn es kann ja sein, dass nur
> der erste Buchstabe des Strings im ersten Reg enthalten
> ist, oder die ersten beiden oder die ersten drei usw. und
> das kann ich doch nicht alles einzeln schreiben.
Einzeln? Und was wenn das Wort länger ist als du es "einzeln" geschrieben hast? Das kann natürlich nie funktionieren wie du dir schon richtig gedacht hast. Die Lösungsidee hast du aber auch schon fast geschrieben: Beim Konkatenieren muss wohl ein Prefix des Worts auf den ersten Ausdruck passen und das verbleibende Suffix auf den zweiten Ausdruck. Angenommen du wüsstest die Länge dieses Prefixes, dann wäre das Problem gelöst - wenn nicht nochmal zurücklehnen und darüber nachdenken
Leider wissen wir diese Länge aber nicht und außerdem kann es auch mehrere mögliche solche Längen geben (was aber egal wäre, da du nur Bool zurücklieferst und das in beiden Fällen klappt). Also müssen wir noch diese Länge herausfinden. Welche Möglichkeiten gibt es nun ein Prefix eines Wortes zu bilden? Es sollte klar sein, dass es dafür n+1 Möglichkeiten gibt bei einem Wort der Länge n (es ist auch [mm] $\varepsilon$ [/mm] und das gesamte Wort ein Prefix). Anstatt nun alles "einzeln" zu schreiben, was spricht dagegen alle diese Prefixe durchzuprobieren?
Betrachten wir mal das Wort "ab". Das Programm würde nun die Aufteilung in [mm] $\varepsilon$ [/mm] und "ab" vornehmen und diese (rekursiv) darauf prüfen, ob sie auf die beiden Ausdrücke des Cat passen. Wenn ja fertig, wenn nein weiter mit "a" und "b" und nochmal testen. Wenn nein weiter mit "ab" und [mm] $\varepsilon$ [/mm] und wenn das auch nicht passt gibt es ein False zurück, weil offensichtlich keine gültige Konkatenation gemäß der beiden Ausdrücke bei der Erzeugung des Wortes stattgefunden hat.
> Ich hoffe, es ist irgendwie klar geworden, was ich meine -
> irgendwie bekomme ich das gerade nicht besser formuliert...
> Evtl. kannst du mir einen Tipp geben - auch erstmal nicht
> unbedingt direkt auf Haskell bezogen...
Das oben war unabhängig von Haskell. Für die Implementierung würde ich dir empfehlen eine Hilfsfunktion einzuführen, die diese Aufteilungen durchprobiert. Das Aufteilen kannst du in Haskell bequem mit splitAt :: Int -> [a] -> ([a], [a]) machen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:51 Mo 14.11.2005 | | Autor: | Bastiane |
Hallo Frank!
Vielen Dank für deine Hilfen - ich glaube, ich habe es vorhin (nach drei Stunden oder so...) endlich hinbekommen (ich hoffe jedenfalls, dass es so richtig ist, wüsste aber nicht, wieso nicht. ).
Ich poste mal einfach meine Lösung und auch noch die Aufgabe davor - falls du Lust hast, kannst du es dir ja angucken, ansonsten betrachte es einfach als "Speicher" für meine Aufgabe - falls ich meine Datei irgendwann nicht mehr finden sollte oder so...
Also die zweite Aufgabe war:
Schreibe eine Funktion
containsEps :: Reg -> Bool
die überprüft, ob das leere Wort ("") in der von dem regulären Ausdruck bezeichneten Sprache enthalten ist. (wiederum effizienter als es auf language zurückzuführen)
Meine Lösung:
containsEps :: Reg -> Bool
containsEps Eps = True
containsEps (Sym zeichen) = False
containsEps (Alt a b) = (containsEps a) || (containsEps b)
containsEps (Cat a b) = (containsEps a) && (containsEps b)
Und nun meine Lösung zur dritten Aufgabe:
matches :: String -> Reg -> Bool
matches "" b = containsEps b
matches [x] (Sym zeichen) = (x==zeichen)
matches (x:xs) Eps = False
matches (x:xs) (Sym zeichen) = False
matches (x:xs) (Cat a b) = or [(matches (first (splitAt i (x:xs))) a) && (matches (second (splitAt i (x:xs))) b)|i <- [0..length (x:xs)]]
matches (x:xs) (Alt a b) = (matches (x:xs) a) || (matches (x:xs) b)
first :: ([Char],[Char]) -> [Char]
first ("",(y:ys)) = ""
first ((x:xs),"") = (x:xs)
first ((x:xs),(y:ys)) = (x:xs)
second :: ([Char],[Char]) -> [Char]
second ("",(y:ys)) = (y:ys)
second ((x:xs),"") = ""
second ((x:xs),(y:ys)) = (y:ys)
Mein Problem bei matches (x:xs) (Cat a b) war gewesen, dass ich vergessen hatte, dass das Ganze ja rekursiv geht - das fiel mir dann erst nach ein paar Stunden ein...
Danke auch für den Tipp mit splitAt - da hätte ich doch noch ne Zeit überlegen müssen, bis ich dadrauf gekommen wäre und es hätte benutzen können...
Viele Grüße
Bastiane
|
|
|
|
