[Anwendungen zum Stack] [TOP]
Der Stapel als grundlegende Datenstruktur kann in Haskell auf verschiedene
Weise implementiert werden. Die definierten Methoden auf einem Stack sind
weitestgehend identisch. Allerdings gibt es Unterschiede bzw. verschiedene
Herangehensweisen, von denen einige nachfolgend vorgestellt werden.
Ein Stapel selbst ist nach dem LIFO (Last In - First Out) Prinzip organisiert.
Die Spezifikation der wichtigsten Methoden :
Die Implementierung des Datentyps Stack als Listetyp
Die Verwendung eines Typsynonyms gestattet eine einfache Implementierung der Stackfunktionen. Der Vorteil ist hierbei die Möglichkeit des Zugriffs auf die eingebauten Listenfunktionen. Damit ist der Stack aber auch von außen veränderbar. Die Zeile test = 2 : (push 5 new) würde in der nachfolgenden Implementierung eine Ausgabe liefern !?
01 type Stack = Int 02 03 new :: Stack 04 push :: Int -> Stack -> Stack 05 pop :: Stack -> Stack 06 top :: Stack -> Int 07 isempty :: Stack -> Bool 08 09 new = [] 10 11 push a [] = [a] 12 push a xs = (a:xs) 13 14 pop [] = error "Stack is empty" 15 pop (x:xs) = xs 16 17 top [] = error "Stack is empty" 18 top (x:xs) = x 19 20 isempty [] = True 21 isempty _ = False |
Der Stack als algebraischer Datentyp
Um sich von den eingebauten Listenfunktionen zu lösen, kann folgender algebraische Datentyp verwendet werden. Hier wird der Listentyp zwar immer noch verwendet, allerdings erfolgt der Zugriff über den Konstruktor S. Um den Datentyp polymorph zu gestalten, ist im Gegensatz zum Beispiel der Definition eines Datentyps Strecke (data Strecke = S Float Float) die Übergabe eines entsprechenden Parameters (in diesem Fall a) erforderlich.
01 data Stack a = S [a] 02 deriving (Show) 03 04 new :: Stack a 05 push :: Int -> Stack a -> Stack a 06 pop :: Stack a -> Stack a 07 top :: Stack a -> a 08 isempty :: Stack a -> Bool 09 10 new = S [] 11 12 push a (S []) = S [a] 13 push a (S xs) = S (a:xs) 14 15 pop (S []) = error "Stack is empty" 16 pop (S (x:xs)) = S xs 17 18 top (S []) = error "Stack is empty" 19 top (S (x:xs)) = x 20 21 isempty (S []) = True 22 isempty (S _) = False |
Eine vollständig vom Listenmodul unabhängige Lösung setzt die rekursive Verwendung des Datentyps voraus. In diesem Zusammenhang ist dann auch die Schaffung einer Instanz von Show sinnvoll um eine mögliche Bildschirmausgabe für den Stack zu realisieren.
01 data Stack a = Empty | S a (Stack a) 03 04 new :: Stack a 05 push :: Int -> Stack a -> Stack a 06 pop :: Stack a -> Stack a 07 top :: Stack a -> a 08 isempty :: Stack a -> Bool 09 10 new = Empty 11 12 push a b = S a b 13 14 pop Empty = error "Stack is empty" 15 pop (S a b) = b 16 17 top Empty = error "Stack is empty" 18 top (S a b) = a 19 20 isempty Empty = True 21 isempty _ = False 22 23 test1 = push 's' (push 't' (push 'a' (push 'c' (push 'k' new)))) 24 test2 = top (test1) |
Die Implementierung einer Showinstanz muss für den übergebenen Parameter abgeleitet werden.
01 instance (Show a) => Show (Stack a) where 03 show = showStack 04 05 showStack Empty = "-|" 06 showStack (S a b) = show a ++ "-" ++ (showStack b) |
01 module Queue (empty, addQ, remQ) 02 where 03 04 -- Spezifikation 05 06 emptyQ :: Qu a 07 addQ :: a -> Qu a -> Qu a 08 remQ :: Qu a -> Qu a 09 isempty :: Qu a -> Bool 10 11 data Qu a = Empty | C a (Qu a) 12 13 -- Implementierung 14 15 emptyQ = Empty 16 17 add a q = C a q 18 19 remQ Empty = error "Queue is empty" 20 remQ (C a Empty) = Empty 21 remQ (C a b) = C a (remQ b) 22 23 isempty Empty = True 24 isempty _ = False 25 26 test1 = addQ 3 (addQ 2 (emptyQ)) 27 test1 = remQ (addQ 3 (addQ 2 (emptyQ))) 28 29 instance (Show a) => Show (Qu a) where 30 show = showStack 31 32 showStack Empty = "-|" 33 showStack (C a b) = show a ++ "-" ++ (showStack b) |