Druh (teorie typů)

Druh je v teorii typů "typ typu". Druh konkrétních typů (např. čísla nebo řetězce) je ${\displaystyle *}$, druh generických typů (např. seznamu List⟨_⟩) je ${\displaystyle *\rightarrow *}$ a druh monád je ${\displaystyle (*\rightarrow *)\rightarrow *}$. V případě monád jde o druh vyššího řádu.

Konkrétní typy (druhu ${\displaystyle *}$) tvoří kategorii, ve které morfismy jsou funkce. Typem druhu ${\displaystyle *\rightarrow *}$ je v C++ například

template<typename T> class A;

Typem druhu ${\displaystyle *\rightarrow *\rightarrow *}$ je například

template<typename T, typename U> class A;

Typem vyššího druhu ${\displaystyle (*\rightarrow *)\rightarrow *}$ je kupříkladu:

template<template<typename> class T> class A;

Ve většině běžných imperativních jazyků (Java, Swift, Go…) není možné typy vyšších druhů používat kvůli chybějící podpoře v překladači a runtimu. V dynamicky typovaných jazycích (Python, Objective-C apod.) je implementace bezproblémová, ovšem bez typové kontroly během překladu.

Kombinátor pevného bodu

Příkladem funkce s typem vyššího druhu je kombinátor pevného bodu, jehož druh je ${\displaystyle ((*\rightarrow *)\rightarrow *\rightarrow *)\rightarrow *\rightarrow *}$. V Haskellu se definuje takto:

fix f = let x = f x in x

neboli

fix f = f (fix f)