Ein beliebiger Boolescher Ausdruck mit dem Wahrheitswert False?

Kann man das mit einem Permutationenalgorythmus verbinden, so daß jeder Test maximal einmal durchgeführt wird?

Ich hatte zuerst eine effizientere Version, aber die hab ich wieder gelöscht, weil sie 2 Funktionen braucht. Vielleicht sollte ich die oder so eine ähnliche nochmal machen. Ich dachte, eine einzige Funktionsdefinition ist schöner, als wenn es 2 Funktionen braucht, aber es gefällt mir gar nicht, daß viele Tests überflüssigerweise mehrfach durchgeführt werden und dazu ja auch jeweils wieder ein Funktionsaufruf notwendig ist.

allDifferent2 :: Eq a => [a] -> Bool
allDifferent2 [] = True
allDifferent2 (x:[]) = True
allDifferent2 (x:y:xs) = (x /= y) && allDifferent2 (x:xs) && allDifferent2 (y:xs)

allDifferent3 :: Eq a => [a] -> Bool
allDifferent3 [] = True
allDifferent3 (x:[]) = True
allDifferent3 (x:y:l)
   | x == y = False
   | otherwise = allDifferent3 (x:l) && allDifferent3 (y:l)

Die Funktion hab ich umbenannt und deshalb dann auch in einen neuen Beitrag allDifferent3 geschrieben, weil ich noch mehrere Algorythmen realisiert habe. Darunter sind auch zwei, die meinem ersten Ansatz nahe kommen und zwei Funktionen benötigen, aber dafür insgesamt effizienter in der Ausführung (Faktor bis > 50) sind.

So ist es länger und man braucht eine Fallunterscheidung, also ist es komplizierter, aber es ist effizienter, also benötigt weniger Reduktionen in den meisten Fällen.

allDifferent4 :: Eq a => [a] -> Bool
allDifferent4 [] = True
allDifferent4 (x:[]) = True
allDifferent4 (x:xs) = notInList x xs && allDifferent4 xs

Das benötigt noch die Funktion:

notInList :: Eq a => a -> [a] -> Bool
notInList _ [] = True
notInList x (y:ys)
   | x == y = False
   | otherwise = notInList x ys

allDifferent5 :: Eq a => [a] -> Bool
allDifferent5 [] = True
allDifferent5 (x:[]) = True
allDifferent5 (x:xs)
   | inList x xs = False
   | otherwise = allDifferent5 xs

-- benötigt noch eine Funktion inList:

inList :: Eq a => a -> [a] -> Bool
inList _ [] = False
inList x (y:ys)
   | x == y = True
   | otherwise = inList x ys

Ohje, mir fallen immer wieder neue Varianten ein mit unterschiedlicher Effizienz. Aber jetzt lassen wir es mal dabei.
Wenn niemand sonst etwas schreibt, ist das nicht besonders anregend.

substring :: String -> String -> Bool
substring [] _ = True
substring _ [] = False
substring (e:es) (c:cs) = (e == c && substring es cs) || substring (e:es) cs

Aufgabe 4 konnte ich leider nicht mehr fertig bearbeiten, weil mich ein kleiner dicklicher dunkelhaariger Hausmeister massiv daran gehindert hat, weiter zu arbeiten. Er hat sogar intelligenterweise sofort das Licht im CIP-Pool komplett ausgeschaltet, nachdem er scheinbar die vordere Türe abgeschlossen hatte, als ich dabei war, die Arbeiten zu speichern, die einzelnen Programme ordnungsgemäß zu beenden und mich auszuloggen, um mich an diesen notwendigen Arbeiten zu hindern.

Beim längeren konzentrierten Arbeiten vergesse ich im Allgemeinen wegen der Konzentration den Verlauf der Zeit und so war ich um 21:22 Uhr noch im CIP-Pool angestrengt bei dem Bearbeiten der Info 1 Aufgaben, als der erwähnte Hausmeister zunächst kaum hörbar herinplatzte, nachdem ein Tarnkommilitone seine blödsinnige nervige und wenig sinnvolle Ausfragerei beendet hatte und mich endlich an dem Übungsblatt weiter arbeiten ließ.

Als ich den Hausmeister bat, das Licht im Raum noch kurz an zu lassen, damit ich mich ordnungsgemäß ausloggen könne, wurde dieser ausfallend und begann einen ersten Satz mit "Des kotzt mi a ...", den ich hier lieber nicht in Gänze öffentlich ausführen möchte.
So dauerte der Ausloggprozess mit den davor notwendigen Arbeiten leider dank dem rüden und intelligenten Verhalten dieses Hausmeisters ein Vielfaches länger, als es normalerweise mit der notwendigen Beleuchtung gedauert hätte. Schließlich blieb mir nichts anderes übrig, als dazwischen doch nochmal aufzustehen und unter Gefahr der unstetig anwachsenden Unmutäußerungen - wer kann schon wissen, wann diese bei dem angewandten Tonfall von der verbalen Ebene auf handfeste körperliche Attacken ausgeweitet werden? - dieses Hausmeisters zitternd vor Angst ein Licht einzuschalten, was mir dann erst das Durchführen der notwendigen Arbeiten zum Beenden der Sitzung ermöglichte. Das veranlasste ihn dann zu der Drohung, mich komplett im CIP-Raum einzusperren.

Das hab ich immer noch nicht hinbekommen.
Hat das schon wer?
Hier ist mal das, was ich bis jetzt habe:

klammerInhalt :: [a] -> [a]
klammerInhalt xs = tail (init (xs))

isGeklammert :: Eq a => a -> a -> [a] -> Bool
isGeklammert o s xs = (head xs == o) && (last xs == s)

isHtmlKlammer :: [[Char]] -> Bool
isHtmlKlammer = isGeklammert "<html>" "</html>"
isHeadKlammer :: [[Char]] -> Bool
isHeadKlammer = isGeklammert "<head>" "</head>"
isTitleKlammer :: [[Char]] -> Bool
isTitleKlammer = isGeklammert "<title>" "</title>"
isMetaKlammer :: [[Char]] -> Bool
isMetaKlammer = isGeklammert "<meta>" "</meta>"
isBodyKlammer :: [[Char]] -> Bool
isBodyKlammer = isGeklammert "<body>" "</body>"


listeBis :: Eq a => a -> [a] -> [a]
listeBis _ [] = []
listeBis e (x:xs)
   | e == x = [x]
   | otherwise = x : listeBis e xs


anfKlammer :: (Eq a, Show a) => a -> a -> [a] -> [a]
anfKlammer _ _ [] = []
anfKlammer o s (x:xs)
   | notInList s xs = error("Uebungsblatt_06.anfKlammer: Klammerungsfehler: " ++ show (xs) ++ " enthält die schließende Klammer " ++ show s ++ " nicht.")
   | o == x = x : listeBis s xs
   | otherwise = error ("Uebungsblatt_06.anfKlammer: Klammerungsfehler: " ++ show (x:xs) ++ " beginnt nicht mit " ++ show o ++ ".")


trenneAnfKlammernAb :: String -> String -> Char -> [String] -> [[String]]
trenneAnfKlammernAb _ _ _ [] = [[]]
trenneAnfKlammernAb o s a (x:xs)
   | a == '1' =
      if x == o && inList s xs then
         let ak = anfKlammer o s (x:xs) in
            ak : [drop (length ak - 1) xs]
      else [x:xs]
   | a == '*' =
      if x == o && inList s xs then
         let ak = anfKlammer o s (x:xs) in
            ak : trenneAnfKlammernAb o s a (drop (length ak - 1) xs)
      else [x:xs]
   | a == '+' =
      if x == o && inList s xs then
         let ak = anfKlammer o s (x:xs) in
            ak : trenneAnfKlammernAb o s '*' (drop (length ak - 1) xs)
      else error ("Uebungsblatt_06.trenneAnfKlammernAb: Aktion " ++ show a ++ ": Klammerpaar " ++ show o ++ " - " ++ show s ++ " nicht in " ++ show (x:xs) ++ " enthalten.")
   | otherwise = error ("Uebungsblatt_06.trenneAnfKlammernAb: Aktion " ++ show a ++ " nicht definiert.")




hatBodyKlasse _ = True
hatHeadKlasse _ = True


checkHTML :: String -> Bool
checkHTML s = let w = words s
                  i = klammerInhalt w in
   isHtmlKlammer w && hatHeadKlasse i && hatBodyKlasse i

trenneAnfHeadAb = trenneAnfKlammernAb "<head>" "</head>" '1'
trenneAnfTitleAb = trenneAnfKlammernAb "<title>" "</title>" '1'
trenneAnfMetasAb = trenneAnfKlammernAb "<meta>" "</meta>" '*'

klammerAnListAnf o s (x:xs)
   | o == x && inList s xs = True
   | otherwise = False

headAnListAnf = klammerAnListAnf "<head>" "</head>"
titleAnListAnf = klammerAnListAnf "<title>" "</title>"
metaAnListAnf = klammerAnListAnf "<meta>" "</meta>"
bodyAnListAnf = klammerAnListAnf "<body>" "</body>"

isHeadBodyKlassen xs
   | headAnListAnf xs = isHead hl && notInList "<head>" rL && notInList "</head>" rL && isBody rL
     where headTrenn = trenneAnfHeadAb xs
           hL = head headTrenn
           rL = tail headTrenn
           isHead hL = isHeadKlammer hL && isTitleMetaKlassen hI
              where hI = klammerInhalt hL
                    isTitleMetaKlassen hI
                       | titleAnListAnf hI = isTitle titL && notInList "<title>" titRL && notInList "</title>" titRL && isMetaKlassen titRL
                          where titTrenn = trenneAnfTitleAb hI
                                titL = head titTrenn
                                titRL = tail titTrenn
                                isTitle titL = isTitleKlammer titL
                                isMetaKlassen titRL
                                   | titRL == [] = True
                                   | metaAnListAnf titRL = isMetas mL && mRL == []
                                      where mTr = trenneAnfMetasAb titRL
                                            mL = init mTr
                                            mRL = last mTr
                                            isMetas [] = True
                                            isMetas (m:ms) = isMetaKlammer m && isMetas ms
                                   | otherwise = False
                       | otherwise = False
           isBody rL = isBodyKlammer rL
   | otherwise = False


checkHTML :: String -> Bool
checkHTML s = let w = words s
                  i = klammerInhalt w
                  in isHtmlKlammer w && isHeadBodyKlassen i



isHeadBodyKlassen liefert beim Laden beim Parsen einen Syntax Error:

ERROR "uebbl06.hs":144 - Syntax error in input (unexpected `|')

Weiß jemand, was da falsch ist?

module Test_checkHTML (tCH)
   where

tCH :: (String -> Bool) -> IO ()
tCH f = putStr (tch htmlTestList)
   where tch [] = ""
         tch (s:htl) = "f " ++ show s ++ " = " ++ show (f s) ++ "\n" ++ tch htl
         htmlTestList = [ html0, html1, html2, html3, html4, khtml0, khtml1, khtml2, khtml3, khtml4, khtml5, khtml6, khtml7, khtml8 ]
         html0 = "<html> <head> <title> </title> </head> <body> </body> </html>"
         html1 = "<html> <head> <title> </title> <meta> </meta> </head> <body> </body> </html>"
         html2 = "<html> <head> <title> </title> <meta> </meta> <meta> </meta> </head> <body> </body> </html>"
         html3 = "<html> <head> <title> </title> <meta> </meta> <meta> </meta> <meta> </meta> </head> <body> </body> </html>"
         html4 = "<html> <head> <title> </title> <meta> </meta> <meta> </meta> <meta> </meta> <meta> </meta> </head> <body> </body> </html>"
         khtml0 = "<html> <head> <title> </title> </head> <body> </body> "
         khtml1 = "<html> <head> <title> </title> </head> <body> </body> </htmll>"
         khtml2 = "<head> <title> </title> </head> <body> </body> </html>"
         khtml3 = "<html> <head> <title> Hallo Leute! </title> </head> <body> </body> </html>"
         khtml4 = "<html> <head> <title> </title> <meta name=\"test\" value=\"blafasel\"> </meta> <meta> </meta> </head> <body> </body> </html>"
         khtml5 = "<html> <head> <title> </title> <meta> </meta> <meta> MetaInhalt </meta> </head> <body> </body> </html>"
         khtml6 = "<html> <head> <title> </title> <meta> </meta> <meta> </meta> </head> <body> </body> </khtml>"
         khtml7 = "<html> <head> <title> </title> <meta> </meta> <meta> </meta> </head> <body> HTML-Text, der angezeigt wird, oder auch nicht... </body> </html>"
         khtml8 = "<html> <head> <meta> </meta> <meta> </meta> </head> <body> </body> </html>"

Das kann man als Datei z.B. "testCheckHtml.hs" speichern und dann mit ":also <dateipfad>" zu seinem Modul dazuladen.
Zum Verwenden der Funktion, ohne sie in seine Datei rein zu kopieren, muß man aber noch irgendetwas machen. Importieren sollte gehen, aber vielleicht geht es auch, ohne eine der beiden Dateien zu verändern, was wünschenwert wäre.

Dann kann man mit

tCH checkHTML

oder allgemein

tCH <Funktionsname>

seine Funktion mit den gespeicherten Teststrings durchtesten lassen und nachsehen, ob die Ausgabe stimmt.

tCH braucht als Argument natürlich eine Funktion mit der Funktionalität String -> Bool.

checkHTML :: String -> Bool
checkHTML s = isAnf sa && isMetas sm && isEnde se
   where sw = words s
         anf = ["<html>","<head>","<title>","</title>"]
         meta = ["<meta>","</meta>"]
         end = ["</head>","<body>","</body>","</html>"]
         sa = take (length anf) sw
         soa = drop (length anf) sw
         se = drop (length sw - length end) sw
         sm = take (length soa - length end) soa
         isAnf sa = sa == anf
         isMetas [] = True
         isMetas sm | sm == [] = True
                    | take 2 sm /= meta = False
                    | otherwise = isMetas (drop 2 sm)
         isEnde se = se == end

So, nun hab ich euch noch schnell eine Primitivstversion von checkHTML geschrieben, weil ich den Fehler in der Funktionsdefinition von isHeadBodyKlassen nicht finden kann.
Naja, für genau die vorgegebene Grammatik tut sies ja, aber zu mehr ist die Funktion nicht zu gebrauchen. :-( Fürs Übungsblatt genügt das hoffentlich.

euer amo

module Uebungsblatt_06
   ( allDifferent,
     substring,
     checkHTML )
   where


allDifferent2 :: Eq a => [a] -> Bool
allDifferent2 [] = True
allDifferent2 (x:[]) = True
allDifferent2 (x:y:xs) = (x /= y) && allDifferent2 (x:xs) && allDifferent2 (y:xs)


allDifferent3 :: Eq a => [a] -> Bool
allDifferent3 [] = True
allDifferent3 (x:[]) = True
allDifferent3 (x:y:l)
   | x == y = False
   | otherwise = allDifferent3 (x:l) && allDifferent3 (y:l)


allDifferent4 :: Eq a => [a] -> Bool
allDifferent4 [] = True
allDifferent4 (x:[]) = True
allDifferent4 (x:xs) = notInList x xs && allDifferent4 xs


allDifferent :: Eq a => [a] -> Bool
allDifferent [] = True
allDifferent (x:[]) = True
allDifferent (x:xs)
   | inList x xs = False
   | otherwise = allDifferent xs


inList :: Eq a => a -> [a] -> Bool
inList _ [] = False
inList x (y:ys)
   | x == y = True
   | otherwise = inList x ys


notInList :: Eq a => a -> [a] -> Bool
notInList _ [] = True
notInList x (y:ys)
   | x == y = False
   | otherwise = notInList x ys


substring :: String -> String -> Bool
substring [] _ = True
substring _ [] = False
substring (e:es) (c:cs) = (e == c && substring es cs) || substring (e:es) cs


klammerInhalt :: [a] -> [a]
klammerInhalt xs = tail (init (xs))

isGeklammert :: Eq a => a -> a -> [a] -> Bool
isGeklammert o s xs = (head xs == o) && (last xs == s)

isHtmlKlammer :: [[Char]] -> Bool
isHtmlKlammer = isGeklammert "<html>" "</html>"
isHeadKlammer :: [[Char]] -> Bool
isHeadKlammer = isGeklammert "<head>" "</head>"
isTitleKlammer :: [[Char]] -> Bool
isTitleKlammer = isGeklammert "<title>" "</title>"
isMetaKlammer :: [[Char]] -> Bool
isMetaKlammer = isGeklammert "<meta>" "</meta>"
isBodyKlammer :: [[Char]] -> Bool
isBodyKlammer = isGeklammert "<body>" "</body>"


listeBis :: Eq a => a -> [a] -> [a]
listeBis _ [] = []
listeBis e (x:xs)
   | e == x = [x]
   | otherwise = x : listeBis e xs


anfKlammer :: (Eq a, Show a) => a -> a -> [a] -> [a]
anfKlammer _ _ [] = []
anfKlammer o s (x:xs)
   | notInList s xs = error("Uebungsblatt_06.anfKlammer: Klammerungsfehler: " ++ show (xs) ++ " enthält die schließende Klammer " ++ show s ++ " nicht.")
   | o == x = x : listeBis s xs
   | otherwise = error ("Uebungsblatt_06.anfKlammer: Klammerungsfehler: " ++ show (x:xs) ++ " beginnt nicht mit " ++ show o ++ ".")


trenneAnfKlammernAb :: String -> String -> Char -> [String] -> [[String]]
trenneAnfKlammernAb _ _ _ [] = [[]]
trenneAnfKlammernAb o s a (x:xs)
   | a == '1' =
      if x == o && inList s xs then
         let ak = anfKlammer o s (x:xs)
             in ak : [drop (length ak - 1) xs]
      else [x:xs]
   | a == '*' =
      if x == o && inList s xs then
         let ak = anfKlammer o s (x:xs)
             in ak : trenneAnfKlammernAb o s a (drop (length ak - 1) xs)
      else [x:xs]
   | a == '+' =
      if x == o && inList s xs then
         let ak = anfKlammer o s (x:xs)
             in ak : trenneAnfKlammernAb o s '*' (drop (length ak - 1) xs)
      else error ("Uebungsblatt_06.trenneAnfKlammernAb: Aktion " ++ show a ++ ": Klammerpaar " ++ show o ++ " - " ++ show s ++ " nicht in " ++ show (x:xs) ++ " enthalten.")
   | otherwise = error ("Uebungsblatt_06.trenneAnfKlammernAb: Aktion " ++ show a ++ " nicht definiert.")


trenneAnfHeadAb = trenneAnfKlammernAb "<head>" "</head>" '1'
trenneAnfTitleAb = trenneAnfKlammernAb "<title>" "</title>" '1'
trenneAnfMetasAb = trenneAnfKlammernAb "<meta>" "</meta>" '*'

klammerAnListAnf o s (x:xs)
   | o == x && inList s xs = True
   | otherwise = False

headAnListAnf = klammerAnListAnf "<head>" "</head>"
titleAnListAnf = klammerAnListAnf "<title>" "</title>"
metaAnListAnf = klammerAnListAnf "<meta>" "</meta>"
bodyAnListAnf = klammerAnListAnf "<body>" "</body>"

{--
isHeadBodyKlassen xs
   | headAnListAnf xs = isHead hl && notInList "<head>" rL && notInList "</head>" rL && isBody rL
     where headTrenn = trenneAnfHeadAb xs
           hL = head headTrenn
           rL = tail headTrenn
           isHead hL = isHeadKlammer hL && isTitleMetaKlassen hI
              where hI = klammerInhalt hL
                    isTitleMetaKlassen hI
                       | titleAnListAnf hI = isTitle titL && notInList "<title>" titRL && notInList "</title>" titRL && isMetaKlassen titRL
                          where titTrenn = trenneAnfTitleAb hI
                                titL = head titTrenn
                                titRL = tail titTrenn
                                isTitle titL = isTitleKlammer titL
                                isMetaKlassen titRL
                                   | titRL == [] = True
                                   | metaAnListAnf titRL = isMetas mL && mRL == []
                                      where mTr = trenneAnfMetasAb titRL
                                            mL = init mTr
                                            mRL = last mTr
                                            isMetas [] = True
                                            isMetas (m:ms) = isMetaKlammer m && isMetas ms
                                   | otherwise = False
                       | otherwise = False
           isBody rL = isBodyKlammer rL
   | otherwise = False


checkHTML :: String -> Bool
checkHTML s = let w = words s
                  i = klammerInhalt w
                  in isHtmlKlammer w && isHeadBodyKlassen i

--}

checkHTML :: String -> Bool
checkHTML s = isAnf sa && isMetas sm && isEnde se
   where sw = words s
         anf = ["<html>","<head>","<title>","</title>"]
         meta = ["<meta>","</meta>"]
         end = ["</head>","<body>","</body>","</html>"]
         sa = take (length anf) sw
         soa = drop (length anf) sw
         se = drop (length sw - length end) sw
         sm = take (length soa - length end) soa
         isAnf sa = sa == anf
         isMetas [] = True
         isMetas sm | sm == [] = True
                    | take 2 sm /= meta = False
                    | otherwise = isMetas (drop 2 sm)
         isEnde se = se == end


tCH :: IO ()
tCH = putStr (tch htmlTestList)
   where tch [] = ""
         tch (s:htl) = "checkHTML " ++ show s ++ " = " ++ show (checkHTML s) ++ "\n" ++ tch htl
         htmlTestList = [ html0, html1, html2, html3, html4, khtml0, khtml1, khtml2, khtml3, khtml4, khtml5, khtml6, khtml7, khtml8 ]
         html0 = "<html> <head> <title> </title> </head> <body> </body> </html>"
         html1 = "<html> <head> <title> </title> <meta> </meta> </head> <body> </body> </html>"
         html2 = "<html> <head> <title> </title> <meta> </meta> <meta> </meta> </head> <body> </body> </html>"
         html3 = "<html> <head> <title> </title> <meta> </meta> <meta> </meta> <meta> </meta> </head> <body> </body> </html>"
         html4 = "<html> <head> <title> </title> <meta> </meta> <meta> </meta> <meta> </meta> <meta> </meta> </head> <body> </body> </html>"
         khtml0 = "<html> <head> <title> </title> </head> <body> </body> "
         khtml1 = "<html> <head> <title> </title> </head> <body> </body> </htmll>"
         khtml2 = "<head> <title> </title> </head> <body> </body> </html>"
         khtml3 = "<html> <head> <title> Hallo Leute! </title> </head> <body> </body> </html>"
         khtml4 = "<html> <head> <title> </title> <meta name=\"test\" value=\"blafasel\"> </meta> <meta> </meta> </head> <body> </body> </html>"
         khtml5 = "<html> <head> <title> </title> <meta> </meta> <meta> MetaInhalt </meta> </head> <body> </body> </html>"
         khtml6 = "<html> <head> <title> </title> <meta> </meta> <meta> </meta> </head> <body> </body> </khtml>"
         khtml7 = "<html> <head> <title> </title> <meta> </meta> <meta> </meta> </head> <body> HTML-Text, der angezeigt wird, oder auch nicht... </body> </html>"
         khtml8 = "<html> <head> <meta> </meta> <meta> </meta> </head> <body> </body> </html>"


-- trenneAnfKlammernAb "<html>" "</html>" '1' ["<html>","<head>","<title>","</title>","<meta>","</meta>","<meta>","</meta>","<meta>","</meta>","<meta>","</meta>","<meta>","</meta>","<meta>","</meta>","</head>","<body>","</body>","</html>"]