Algebraische Datentypen

= "`konkrete"' Datentypen,

Konstruktion der Elemente des Types liegt offen und ist Basis für

• Benennung einzelner Elemente
• Definition von Funktionen über dem Typ

Beispiel: Seite

Beachte:

• linke Seite: Schlüsselwort ``data'', dann Typname
• rechte Seite: Konstruktionsschema für Elemente des Typs, unter Verwendung von:
  • Alternativsymbol ``|''
  • andere Typen
  • Konstruktoren, d.h. 0,1,2 ...stellige Funktionen
• Interpretation: zum Typ gehört alles, was sich aus wiederholter Anwendung des Konstruktionschemas erzeugen läßt, vgl. Mathematik:

  
  

  
  
  
  
  
  
  

  in Haskell-Stil:

   data N = Zero | Succ N
  
  
  

 


--------------------- algebraic data types

----------------------- simple examples






data PrimaryColour = Yellow | Red | Blue   - enumeration type






data Points = Point Float Float  - typle type, based on Float






type Name = String

type MatrNr = Int

data StudId = Stud Name MatrNr

                        - record type, based on type synonyms






data Pairs a = Pair a a

                - polymorphic type, based on arbitrary type a






data Union a b = Fst a | Snd b

               - union type, based on arbitrary types a and b






data Tree a = Inner a (Tree a) (Tree a) | Leaf a

                                 - recursive polymorphic type






{-

Main> :t Stud "Franz Gans" 4711

Stud "Franz Gans" 4711 :: StudId

Main> :t Point 0.0 0.0

Point 0.0 0.0 :: Points

Main> :t Leaf "Franz Ganz"

Leaf "Franz Ganz" :: Tree [Char]

Main> :t Fst 3.14

Fst 3.14 :: Fractional a => Union a b

Main> :t Inner 1 (Inner 2 (Leaf 3) (Leaf 4)) (Leaf 5)

Inner 1 (Inner 2 (Leaf 3) (Leaf 4)) (Leaf 5) :: Num a => Tree a

Main> Inner 1 (Inner 2 (Leaf 3) (Leaf 4)) (Leaf 5)






ERROR: Cannot find "show" function for:

*** expression : Inner 1 (Inner 2 (Leaf 3) (Leaf 4)) (Leaf 5)

*** of type    : Tree Int

-}

beachte:

• Großbuchstaben;
• Typname darf als Konstruktorbezeichner verwendet werden, also zB:

   data Point a = Point a a
  
  
  

Unterscheide:

Konstruktorfunktionen und "`Programm"'-Funktionen:

1.

Konstruktorfunktionen erlauben keine Auswertung im Sinne einer Reduktion auf einen einfacheren Wert; sowas wie

 Inner 1 (Inner 1 (Leaf 1) (Leaf 2)) (Leaf 3)

ist Darstellung von

   

     4  
    / \ 
   1   3
  / \   
 1   2  

Situation ist völlig analog zu eingebauten Datentypen, außer daß die keine Wortsymbole verwenden, zB: : und [] für Listen.

2.

Konstruktoren dürfen in patterns auftreten und erlauben so die Definition von Funktionen über dem Datentyp.

 ----------------------some Tree functions






data Tree a = Inner a (Tree a) (Tree a) | Leaf a

                                 - recursive polymorphic type






miniTree = Inner 1 (Inner 2 (Leaf 3) (Leaf 4)) (Leaf 5)






listInorderTree :: (Show a) => Tree a -> String

listInorderTree (Leaf x) = show x

listInorderTree (Inner x yt zt)

      = "<" ++ (listInorderTree yt) ++

                  "<" ++ (show x) ++ ">" ++

                           (listInorderTree zt) ++ ">"






{-

Main> listInorderTree miniTree

"<<3<2>4><1>5>"

-}






sizeOfTree :: Tree a -> Int

sizeOfTree (Leaf x) = 1

sizeOfTree (Inner x yt zt) = 1 + (sizeOfTree yt) + (sizeOfTree zt)






mapTree :: (a->b) -> Tree a -> Tree b

mapTree f (Leaf x) = Leaf (f x)

mapTree f (Inner x yt zt) = (Inner (f x) (mapTree f yt) (mapTree f zt))






{-

Main> listInorderTree miniTree

"<<3<2>4><1>5>"

Main> sizeOfTree miniTree

5

Main> listInorderTree (mapTree (*100) miniTree)

"<<300<200>400><100>500>"

-}

Beispiel:

 -------------------SuchBaeme






data Ord a => STree a = Node a (STree a) (STree a) | Nil

        - polymorphic tree type with constrained on base type

        - note: empty leaves






insertSTree :: Ord a => a -> STree a -> STree a

insertSTree x Nil = Node x Nil Nil

insertSTree x (Node y left right)

   | x<=y       = Node y (insertSTree x left) right

   | otherwise  = Node y left (insertSTree x right)






elemSTree :: Ord a => a -> STree a -> Bool

elemSTree x Nil = False

elemSTree x (Node y left right)

   | x==y       = True

   | x<y        = elemSTree x left

   | otherwise  = elemSTree x right






listToSTree :: Ord a => [a] -> STree a

listToSTree = foldr insertSTree Nil






sTreeToList :: Ord a => STree a -> [a]

sTreeToList Nil = []

sTreeToList (Node x left right)

   = (sTreeToList left) ++ [x] ++ (sTreeToList right)






miniList = [1,5,-3,6,0,99,4,4,55,1000,-1000]






{-

Main> :t Node 3.14 Nil Nil

Node 3.14 Nil Nil :: (Ord a, Fractional a) => STree a

Main> :t Node cos Nil Nil






ERROR: a -> a is not an instance of class ``Ord''

Main> elemSTree 0 (listToSTree miniList)

True

Main> elemSTree 77 (listToSTree miniList)

False

Main> (sTreeToList.listToSTree) miniList  - sort!

[-1000, -3, 0, 1, 4, 4, 5, 6, 55, 99, 1000]

Main> (sTreeToList.listToSTree) (map abs miniList)

[0, 1, 3, 4, 4, 5, 6, 55, 99, 1000, 1000]

-}