Rekursiv definierte Typen

Haskell (http://haskell.org/)

data Tree a = Leaf a 
            | Branch ( Tree a ) ( Tree a )
data List a = Nil | Cons a ( List a )

Java

interface Tree<A> { }
class Leaf<A> implements Tree<A> { A key }
class Branch<A> implements Tree<A> 
  { Tree<A> left, Tree<A> right }

das ist ein algebraischer Datentyp,

die Konstruktoren (Leaf, Nil) bilden die Signatur der Algebra,

die Elemente der Algebra sind Terme (Bäume)



Johannes Waldmann 2013-01-28