Haskell Rekursive und zyklische Datenstrukturen

Beispiel Labyrinth

Modellierung

• Ein (gerichtetes) Labyrinth ist entweder
  • eine Sackgasse oder
  • ein Weg oder
  • eine Abzweigung (zwei Richtungen)
• Jeder Knoten hat ein Label des Typs a

data Lab a = Dead a   
           | Pass a (Lab a)   
           | TJnc a (Lab a) (Lab a)  

Rekursive Definition in Haskell:

lab0 = Pass 0 lab1   
lab1 = TJnc 1 lab0 lab5   
lab2 = Pass 2 lab1   
lab3 = Dead 3   
lab4 = TJnc 4 lab0 lab3   
lab5 = Pass 5 lab4  

Labyrinth nicht zyklenfrei!

Ausgabe in GHCi (eigene Instanz der Typklasse Show):

> lab2   
2 --> 1   
1 --> 0 5   
0 --> 1   
5 --> 4   
4 --> 0 3   
3 -->  

Traversion von Labyrinthen

Traversion = Pfad zu einem gegebenen Zielknoten finden

Ein Pfad ist eine Liste von Knoten:

type Path a = [a]  
type Trav a = Maybe [a]  

Ohne Zyklen

traverse_1 :: Eq a => a -> Lab a -> Trav a   
traverse_1 t l   
	| nid l == t = Just [nid l]   
	| otherwise = case l of   
	  Dead _ -> Nothing   
	  Pass i n -> cons i (traverse_1 t n)   
	  TJnc i n m -> cons i (select (traverse_1 t n) (traverse_1 t m))  
  
-- mit:   
nid :: Lab a -> a   
nid (Dead i)     = i   
nid (Pass i _)   = i   
nid (TJnc i _ _) = i  
  
-- Propagation von Fehlschlägen in:  
cons :: a -> Trav a -> Trav a   
cons _ Nothing   = Nothing   
cons i (Just is) = Just (i:is)  
  
-- und   
select :: Trav a -> Trav a -> Trav a   
select Nothing t = t   
select t _       = t  

Mit Zyklen

traverse_2 :: Eq a => a -> Lab a -> Trav a   
traverse_2 t l = trav_2 l [] where   
	trav_2 l p | nid l == t = Just (reverse (nid l: p))   
			   | elem (nid l) p = Nothing   
			   | otherwise = case l of   
			     Dead _ -> Nothing   
			     Pass i n -> trav_2 n (i: p)   
			     TJnc i n m -> select (trav_2 n (i: p))   
							          (trav_2 m (i: p))