Einschränkungen in Art Familie Instanzen

Question

Ich erforsche Typen Familien in Haskell, versuchen, die Komplexität der Typ-Level-Funktionen zu etablieren wir definieren können. Ich mag wie so eine geschlossene Typ-Level-Version von mod, etwas definieren:

{-# LANGUAGE TypeFamilies, DataKinds, TypeOperators, UndecidableInstances #-} 
import GHC.TypeLits 

type family Mod (m :: Nat) (n :: Nat) :: Nat where 
    n <= m => Mod m n = Mod (m - n) n 
    Mod m n = m 

jedoch der Compiler (GHC 7.10.2) dies ablehnt, da die Einschränkung in der ersten Gleichung ist nicht gestattet. Wie wirken sich Wächter auf der Werteebene auf die Typenebene aus? Ist das in Haskell derzeit überhaupt möglich?

Answer 1

keine Antwort (ich glaube nicht, es gibt sogar eine mögliche noch) nicht, aber zum Wohle anderer Menschen (wie mich) versucht OPs Schritte in den Kommentaren zurückzuverfolgen. Die folgenden Kompilierungen führen jedoch schnell zu einem Stapelüberlauf.

{-# LANGUAGE TypeFamilies, DataKinds, TypeOperators, UndecidableInstances #-} 
import GHC.TypeLits 
import Data.Type.Bool 

type family Mod (m :: Nat) (n :: Nat) :: Nat where 
    Mod m n = If (n <=? m) (Mod (m - n) n) m 

Der Grund dafür ist, dass If selbst ist nur eine ganz normale Art Familie und das Verhalten von Typ-Familien ist durch die Erweiterung ihre Art Argumente (eifrig in einem gewissen Sinne) zu beginnen, bevor die in der rechten Seite verwenden. Das unglückliche Ergebnis in diesem Fall ist, dass Mod (m - n) n erweitert wird, auch wenn n <=? m falsch ist, damit der Stapelüberlauf.

Aus genau dem gleichen Grund sind die logischen Operatoren in Data.Type.Bool nicht kurzschließen. Angesichts

type family Bottom :: Bool where Bottom = Bottom 

Wir können sehen, dass False && Bottom und True || Bottom beide hängen.

EDIT

Nur für den Fall der OP nur Interesse an einer Art Familie mit dem erforderlichen Verhalten (und nicht nur das allgemeinere Problem, Wachen in Typ Familien) gibt ist ein Weg, um auszudrücken Mod in ein Weg, der endet:

{-# LANGUAGE TypeFamilies, DataKinds, TypeOperators, UndecidableInstances #-} 
import GHC.TypeLits 

type Mod m n = Mod1 m n 0 m 

type family Mod1 (m :: Nat) (n :: Nat) (c :: Nat) (acc :: Nat) :: Nat where 
    Mod1 m n n acc = Mod1 m n 0 m 
    Mod1 0 n c acc = acc 
    Mod1 m n c acc = Mod1 (m - 1) n (c + 1) acc