Datatypes

Datatypes are a complex construct in functional programming languages, combining a number of different features.

• n-ary sums:
  data Day = Sun | ... | Sat
• n-ary products:
  data Complex = Compled Float Float
• abstraction / polymorphism:
  data Maybe $\alpha$ = Nothing | Just $\alpha$
• recursion:
  data List $\alpha$ = Nil | Cons $\alpha$ (List $\alpha$)
• non-uniform recursion / nested datatypes:
  data Perfect $\alpha$ = Tip $\alpha$ | Fork (Perfect ($\alpha$, $\alpha$))
  data Bush $\alpha$ = NilB | ConsB $\alpha$ (Bush (Bush $\alpha$))
• type-constructor polymorphism:
  data GRose $\mathcal{F}$ $\alpha$ = Branch $\alpha$ ($\mathcal{F}$ (GRose $\mathcal{F}$ $\alpha$))
  data Fix $\mathcal{F}$ = In ($\mathcal{F}$ (Fix $\mathcal{F}$))
  data HFix $\mathcal{F}$ $\alpha$ = HIn ($\mathcal{F}$ (HFix $\mathcal{F}$) $\alpha$)