Die Signatur (T, F) einer Datenstruktur besteht aus
einer endlichen Menge T von Typbezeichnern und
einer endlichen Menge F von Funktionsbezeichnern, wobei für jedes f ∈ F ein Funktionstyp f :: T1 → ··· → Tn → T0, Ti ∈ T, 0 ≤ i ≤ n,
definiert ist. n gibt die Stelligkeit von f an.