Grundlagen der Funktionalen Programmierung: Selbstdefinierte Datentypen

data-Deklarationen

für eigene Wertebereiche

Beispiele

data Color = Red | Green | Blue
 
data Move  = Left | Right | Up | Down

Color ist ein Wertebereich mit 3 Werten
Move mit 4 Werten

Red, Green, Blue repräsentieren die 3 Werte von Color
Left, Right, Up, Down die 4 Werte von Move

Red   :: Color
Green :: Color
Blue  :: Color
 
Left  :: Move
Right :: Move
Up    :: Move
Down  :: Move

Red, Green, Blue und Left, Right, Up, Down heißen Konstruktoren

| wird als oder gelesen

Definition

data-Definitionen, die ein | enthalten, heißen Summen-Datentypen

Wahrheitswerte

sind durch eine data-Definition vordefiniert

data Bool = False | True

Konstruktoren dürfen in Mustern verwendet werden

Beispiel

move :: Move -> Position -> Position
 
move Left  (x, y) = (x - 1, y)
move Right (x, y) = (x + 1, y)
move Up    (x, y) = (x, y - 1)
move Down  (x, y) = (x, y + 1)
 
moves :: [Move] -> Position -> Position
 
moves []       p = p
moves (m : ms) p = moves ms (move m p)

[] und : sind die einzigen Konstruktoren für Listen

Vereinfachung

moves besitzt das Rekursionsschema von foldl

	`moves ms p0 = foldl (λ p m -> move m p) p0 ms`
=	{ Definition von flip }
	`moves ms p0 = foldl (flip move) p0 ms`
=	{ Definition von flip }
	`moves = flip (foldl (flip move))`

moves :: [Move] -> Position -> Position
moves = flip (foldl (flip move))
 
-- vordefiniert:
 
flip f = λ x y -> f y x

Konstruktoren

mit Argumenten

Beispiel

data Shape = Circle Float
           | Rectangle Float Float

Werte von Shape

Circle 1.0        :: Shape
Rectangle 2.0 3.0 :: Shape
 
Circle    :: Float -> Shape
Rectangle :: Float -> Float -> Shape

Shape ist die Menge aller mit Circle und aller mit Rectangle konstruierbaren Werte

Konstruktoren können 0, 1, 2, ..., n, ... Argumente besitzen

Die Argumente dürfen unterschiedliche Typen besitzen

Funktionen

mit Shape-Werten

square :: Float -> Shape
square n = Rect n n
 
area :: Shape -> Float
area (Circle r)      = pi * r^2
area (Rectangle w h) = w * h

Polymorphe Datentypen

data-Definitionen

können (wie Typdeklarationen) Typparameter besitzen

Beispiel

data Pair a b = Pair a b
 
data Maybe a  = Nothing
              | Just a

Pair a b ist isomorph zu (a, b)

Paare und n-Tupel sind nur eine bequeme, an die Matematik angelehnte Notation.

Pair a b ist kein Summen-Datentyp, da es nur einen Konstruktor gibt

Wie viele Werte hat Maybe a, wenn a n Werte enthält?

Maybe ist vordefiniert

Anwendung

Aus partiellen Funktionen totale Funktionen machen

-- partiell definiert
 
div :: Integral a => a -> a -> a
div x 0 = error "division by zero"
div x y = ...
 
-- total definiert
 
safeDiv :: Integral a => a -> a -> Maybe a
safeDiv x 0 = Nothing
safeDiv x y = Just (x `div` y)

Der Nutzer von safeDiv wird gezwungen, eine Fehlerüberprüfung zu machen,
bevor mit dem Quotienten weiter gerechnet wird.

Definition

data-Typen mit Typparametern heißen Typkonstruktoren

type MaybeInt = Maybe Int

Verarbeiten

von Maybe-Werten

maybe :: b -> (a -> b) -> Maybe a -> b  -- vordefiniert
 
maybe c f Nothing  = c
maybe c f (Just x) = f x
 
-- Spezialisierung
 
fromMaybe :: a -> Maybe a -> a         -- aus Data.Maybe
fromMaybe c = maybe c id

maybe ist das fold für Maybe-Werte

mapMaybe :: (a -> b) -> Maybe a -> Maybe b
 
mapMaybe f Nothing  = Nothing
mapMaybe f (Just x) = Just (f x)
 
-- oder
 
mapMaybe f = maybe Nothing (Just . f)

mapMaybe ist das map für Maybe-Werte

Selbstdefinierte rekursive Datentypen

Rekursion	In data-Definitionen darf der Typname in der rechten Seite verwendet werden
	rekursive Datenstrukturen

Beispiel	Die natürlichen Zahlen als Peano-Zahlen
	data Nat = Zero \| Succ Nat -- Werte Zero Succ Zero Succ (Succ Zero) Succ (Succ (Succ Zero)) Succ (Succ (Succ (Succ Zero))) Succ (Succ (Succ (Succ (Succ Zero)))) ... -- Addition add :: Nat -> Nat -> Nat add Zero m = m add (Succ n) m = Succ (add n m)
Konversion	von Zahlen in Peano-Darstellung
	intToNat :: Int -> Nat intToNat 0 = Zero intToNat n = Succ (intToNat (n-1)) natToInt :: Nat -> Int natToInt Zero = 0 natToInt (Succ n) = 1 + natToInt n
	intToNat und natToInt bilden einen Isomorphismus zwischen Int und Nat

	Datenstruktur sieht sehr nach einer Liste aus!

Selbst definierte Listen	data List a = Nil \| Cons a (List a) -- [] = Nil -- : = Cons

	Struktur der Algorithmen ableitbar aus der Struktur der Datentypen
Beispiele	sum :: Num a => List a -> a sum Nil = 0 sum (Cons x xs) = x + sum xs
	foldr :: (a -> b -> b) -> b -> List a -> b foldr op c Nil = c foldr op c (Cons x xs) = x `op` foldr op c xs
Listen	Eine rekursive Komponente => Verarbeitung mit linearer Rekursion

Allgemeines Verarbeitungsschema	für beliebige Datentypen
.1	Für jeden Konstruktor gibt es eine Verarbeitungsregel
.2	Alle Komponenten eines Konstruktors werden verarbeitet und zu einem Resultat zusammen gesetzt
.3	Bei einer Rekursion im Datentyp wird die Komponente mit einem rekursiven Aufruf verarbeitet

Bäume	mehrere Rekursionen in der Datenstruktur
Beispiel	Binäre Bäume mit Information an den inneren Knoten
	data Tree a = Null \| Node (Tree a) a (Tree a) type IntTree = Tree Int

Suchen	in einem Baum
	occurs :: Eq a => a -> Tree a -> Bool occurs x Null = False occurs x (Node l y r) = x == y \|\| occurs x l \|\| occurs x r

Transformation	in eine Liste
	flatten :: Tree a -> [a] flatten Null = [] flatten (Node l y r) = flatten l ++ [y] ++ flatten r

	Diese Datenstruktur wird häufig als binärer Suchbaum eingesetzt

Konsistenzbedingung	für binäre Suchbäume
	Für alle Teilbäume gilt: Alle Werte im linken Teilbaum sind kleiner als der Wert an der Wurzel Alle Werte im rechten Teilbaum sind größer als der Wert an der Wurzel

Definition	Solche Konsistenzbedingungen heißen Datenstruktur-Invariante

Invariante	für einen binären Suchbaum
	invSearchTree :: Ord a => Tree a -> Bool invSearchTree Null = True invSearchTree (Node l x r) = lt x l && gt x r && invSearchTree l && invSearchTree r where lt x Null = True lt x (Node l y r) = y < x && lt x l && lt x r gt x Null = True gt x (Node l y r) = y > x && gt x l && gt x r

Suchen	in einem binären Suchbaum
	member :: Ord a => a -> Tree a -> Bool member x Null = False member x (Node l y r) \| x < y = member x l \| x > y = member x r \| otherwise = True
	Suchen im Mittel in logarithmischer Zeit in Abhängigkeit von der Anzahl der Elemente im Baum

Varianten	von Bäumen

Binäre Bäume	mit Information an den Blättern
	data Tree2 a = Leaf a \| Fork (Tree2 a) (Tree2 a)

Bäume	mit beliebig vielen Teilbäumen Rhododendron-Bäume (rose trees)
	data Tree3 a = Node a [Tree3 a]

Beispiele zum Kapitel

module TypeDecl
where
import Prelude hiding ( Left
                      , Right
                      )
-- ----------------------------------------
type Pos = (Int, Int)
data Color
  = Red | Green | Blue
  deriving (Show)
data Move
  = Left | Right | Up | Down
  deriving (Show)
move :: Move -> Pos -> Pos
move Left  (x, y) = (x - 1, y    )
move Right (x, y) = (x + 1, y    )
move Up    (x, y) = (x,     y - 1)
move Down  (x, y) = (x,     y + 1)
moves :: [Move] -> Pos -> Pos
moves ms p0 = foldl (\ p m -> move m p) p0 ms
moves' :: [Move] -> Pos -> Pos
moves' = flip (foldl (flip move))
moves'' :: [Move] -> Pos -> Pos
moves'' ms = foldl (>>>) id fs
  where
    fs    = map move ms
    (>>>) = flip (.)
ms :: [Move]
ms = [Down, Left, Down, Right, Up]
ms0, ms0', ms0'' :: Pos
ms0   = moves   ms (0,0)
ms0'  = moves'  ms (0,0)
ms0'' = moves'' ms (0,0)
-- ----------------------------------------
data Shape
    = Circle Float
    | Rect Float Float
      deriving (Show)
square   :: Float -> Shape
square n = Rect n n
area            :: Shape -> Float
area (Circle r) = pi * r * r
area (Rect w h) = w * h
-- ----------------------------------------
safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv x y = Just (x `div` y)
-- ----------------------------------------
data Nat
    = Zero
    | Succ Nat
      deriving (Show)
intToNat :: Int -> Nat
intToNat 0 = Zero
intToNat n = Succ (intToNat (n-1))
natToInt :: Nat -> Int
natToInt Zero = 0
natToInt (Succ n) = 1 + natToInt n
add :: Nat -> Nat -> Nat
add Zero     n = n
add (Succ m) n = Succ (add m n)
sub :: Nat -> Nat -> Nat
sub n        Zero     = n
sub (Succ m) (Succ n) = sub m n
sub _ _               = error "negative numbers not allowed"
mul :: Nat -> Nat -> Nat
mul Zero _n    = Zero
mul (Succ m) n = (m `mul` n) `add` n
-- ----------------------------------------
data List a
    = Nil
    | Cons a (List a)
      deriving (Show)
-- ----------------------------------------
data IntTree
    = Leaf
    | Node IntTree Int IntTree
      deriving (Show)
t :: IntTree
t = Node
      (Node
        (Node Leaf 1 Leaf)
        3
        (Node Leaf 4 Leaf)
      )
      5
      (Node
        (Node Leaf 6 Leaf)
        7
        (Node Leaf 9 Leaf)
      )
occurs :: Int -> IntTree -> Bool
occurs _m Leaf
    = False
occurs m (Node l n r)
    = m == n
      ||
      occurs m l
      ||
      occurs m r
flatten :: IntTree -> [Int]
flatten Leaf
    = []
flatten (Node l n r)
    = flatten l ++ [n] ++ flatten r
-- ----------------------------------------
data Tree1 a
    = Leaf1 a
    | Node1 (Tree1 a) (Tree1 a)
      deriving (Show)
data Tree2 a
    = Leaf2
    | Node2 (Tree2 a) a (Tree2 a)
      deriving (Show)
data Tree3 a b
    = Leaf3 a
    | Node3 (Tree3 a b) b (Tree3 a b)
      deriving (Show)
data Tree4 a
    = Node4 a [Tree4 a]
      deriving (Show)
-- ----------------------------------------

Selbstdefinierte Datentypen

Typdeklarationen

Neue selbstdefinierte Datentypen

Selbstdefinierte rekursive Datentypen

Beispiele zum Kapitel

Die Quelle