Endlosschleife, wenn alle Werte eines generischen Instanz

Question

Für another answer von mir aufzählt, schrieb ich den folgenden Code, bietet diagonally traversedUniverse Instanzen für zählbare Generic s (es ist leicht von der Version dort aktualisiert, sondern verwendet die gleiche Logik):

{-# LANGUAGE DeriveGeneric, TypeOperators, ScopedTypeVariables #-} 
{-# LANGUAGE FlexibleInstances, FlexibleContexts, DefaultSignatures #-} 
{-# LANGUAGE UndecidableInstances, OverlappingInstances #-} 

import Data.Universe 
import Control.Monad.Omega 
import GHC.Generics 
import Control.Monad (mplus, liftM2) 

class GUniverse f where 
    guniverse :: Omega (f x) 

instance GUniverse U1 where 
    guniverse = return U1 

instance (Universe c) => GUniverse (K1 i c) where 
    guniverse = fmap K1 $ each (universe :: [c])  -- (1) 

instance (GUniverse f) => GUniverse (M1 i c f) where 
    guniverse = fmap M1 (guniverse :: Omega (f p)) 

instance (GUniverse f, GUniverse g) => GUniverse (f :*: g) where 
    guniverse = liftM2 (:*:) ls rs 
     where ls = (guniverse :: Omega (f p)) 
       rs = (guniverse :: Omega (g p)) 

instance (GUniverse f, GUniverse g) => GUniverse (f :+: g) where 
    guniverse = (fmap L1 $ ls) `mplus` (fmap R1 $ rs) -- (2) 
     where ls = (guniverse :: Omega (f p)) 
       rs = (guniverse :: Omega (g p)) 

instance (Generic a, GUniverse (Rep a)) => Universe a where 
    universe = runOmega $ fmap to $ (guniverse :: Omega (Rep a x)) 

(Omega wird wahrscheinlich nicht mit dem Problem, sondern war Teil der Frage.)

Dies ist für die meisten Arten funktioniert, auch rekursiven wie jene:

data T6 = T6' | T6 T6 deriving (Show, Generic) 
data T = A | B T | C T T deriving (Show, Generic) 
data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show, Generic, Eq) 

Beispiele:

*Main> take 5 $ (universe :: [T6]) 
[T6',T6 T6',T6 (T6 T6'),T6 (T6 (T6 T6')),T6 (T6 (T6 (T6 T6')))] 
*Main> take 5 $ (universe :: [T]) 
[A,B A,B (B A),C A A,B (B (B A))] 
*Main> take 5 $ (universe :: [Tree Bool]) 
[Leaf False,Leaf True,Branch (Leaf False) (Leaf False),Branch (Leaf False) (Leaf True),Branch (Leaf True) (Leaf False)] 

Aber beachten Sie, dass oben genannten Typen haben alle ihre rekursive Konstrukteuren nicht an erster Stelle! In der Tat (und das ist das Problem), die folgende divergiert:

*Main> data T7 = T7 T7 | T7' deriving (Show, Generic) 
*Main> take 5 $ (universe :: [T7]) 
*** Exception: <<loop>> 

Ich dachte zuerst, dass vielleicht ist es etwas mit Omegas ‚s Auswerteauftrag, sondern tauscht die linke und rechte Teile in Linie (2) macht nur T7 Arbeit, und T6 scheitern, was ich als korrektes Verhalten erwarten würde.

Mein aktueller Verdacht ist, dass der Anruf zu universe in Zeile (1) zu früh ausgewertet wird. Zum Beispiel weicht die folgende auch, während sollte es genau eine Wert in der Liste, die nicht einmal ausgewertet werden soll:

*Main> data T8 = T8 T8 deriving (Show, Generic) 
*Main> null $ (universe :: [T8]) 
*** Exception: <<loop>> 

Also, die einzige Instanz, T8 (T8 (...) ...), wird innerhalb der Liste ausgewertet , obwohl es nicht benötigt wird! Ich habe keine Ahnung, woher dieser Effekt kommt - ist es die rekursive Verwendung seiner eigenen Universe Instanz? Aber warum verhalten sich "rekursive" Typen wie T6 korrekt, während "rekursive Links" (T7) nicht funktionieren?

Ist das ein striktes Problem? Wenn ja, in welchem ​​Teil des Codes? Meine Universe Instanz? Generic? Und wie man es repariert? Ich verwende GHC 7.6.3, wenn das wichtig ist.

Answer 1

Typen wie T8 können nicht generiert werden. Schauen wir uns an, was die Generika-Version des Universums für T8 tatsächlich reduziert:

t8Universe :: [T8] 
t8Universe = fmap T8 t8Universe 

An keiner Stelle ist ein (:) oder [] hergestellt. Ohne einen anderen nicht-rekursiven Konstruktor, der erfolgreich produziert werden kann, gibt es keine Möglichkeit, Fortschritte zu machen. t8Universe hat genau so viele Elemente wie t8Universe hat, aber das ist kreisförmig, und so Auswertung Schleifen.