List-Monade: verzweigende Rechnungen

instance Monad [] where
    return x  =  [x]
    xs >>= f  =  concat ( map f xs )

concat :: [[a]] -> [a]
concat = foldr (++) []

-- Beispiel: concat [ "frob", "ni", "", "cate" ] = "frobnicate"

Wort-Ersetzungs-Systeme

module Rewrite where

import Prelude hiding (splitAt)
import Sort (unique)
import Monad (guard)
import Rose
import Form

-- ein Wort an einer Stelle durchschneiden

splitAt :: Int -> [a] -> ([a], [a])
splitAt 0 xs       = ([], xs)
splitAt n (x : xs) = let (vorn, hinten) = splitAt (n-1) xs
                     in  (x : vorn, hinten)
splitAt  n []       = ([], []) -- darüber kann man sich streiten

-- Beispiel:  splitAt 3 "frobnicate" = ("fro","bnicate")
--            splitAt 5 "foo"        = ("foo", "")

-- die Liste aller Zerlegungen 

zerlegungen :: [a] -> [([a], [a])]
zerlegungen xs = do
    i <- [ 0 .. length xs ]
    return $ splitAt i xs

-- Beispiel: zerlegungen "frob" 
--           = [("","frob"),("f","rob"),("fr","ob"),("fro","b"),("frob","")]

-- Das benutzen wir bei der Simulation von Wort-Ersetzungs-Systemen.
-- Diese bestehen aus einer Liste von Regeln,
-- d. h. Paaren aus linker und rechter Seite.

type RS = [ (String, String) ]

-- Beispiele
rs1 = [ ("100" , "00110" ) ]
rs2 = [ ("0011", "111000") ]

-- Alle direkten (in einem Schritt erreichbaren) Nachfolger eines Wortes 
-- darunter sind evtl. einige gleiche, die filtern wir raus mit unique
schritt :: RS -> String -> [ String ]
schritt rs w = unique $ do
    (vorn, hinten) <- zerlegungen w
    (links, rechts) <- rs
    let (mitte, rest) = splitAt (length links) hinten
    guard $ mitte == links    
    let w' = vorn ++ rechts ++ rest
    return $ w'

-- alle Nachfolger eines Wortes
baum :: RS -> String -> Rose String
baum rs w = 
    Node { key = w  
	 , children = map (baum rs) (schritt rs w)
	 }

bsp1 =  baum rs1 "0100100"
bsp2 =  baum rs2 "00110011"

• Ist die Termination entscheidbar?
• Enthält jedes nicht terminierende System eine Schleife?

Grammatiken

data Grammatik = Grammatik
               { terminale      :: String
               , nichtterminale :: String
               , startsymbol    :: Char
               , regeln         :: [ (String, String) ]
               }

• Hilfsprogramme, z. B. Feststellen/Prüfen der Form (d. h. des Chomsky-Typs) der Grammatik
• interessante Übungsaufgaben, z. B. "geben Sie eine Grammatik für ..., bei der in jedem Ableitungsschritt höchstens ein ... links von ..." und die entsprechenden Testprogramme (Beispiel)
• Implementierungen von Algorithmen aus der Grundvorlesung, z. B. Chomsky-NF herstellen, oder Greibach-NF, oder Schnitt mit regulärer Sprache, usw.