ricorsione infinita durante l'enumerazione di tutti i valori di un'istanza generico

Question

Per another answer mio, ho scritto il seguente codice, fornendo diagonally traversedUniverse casi per enumerabili Generic s (è un po 'aggiornato dalla versione lì, ma utilizza la stessa logica):

{-# 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 non è probabilmente legato al problema, ma faceva parte della questione.)

Questo funziona per la maggior parte, anche quelli ricorsivi come quelli:

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) 

Esempi:

*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)] 

ma nota che i tipi di cui sopra hanno tutti i loro costruttori ricorsive non al primo posto! In realtà (e questo è il problema), i seguenti diverge:

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

ho pensato che forse c'è qualcosa con ordine di valutazione Omegas s', ma scambiando le parti sinistra e destra, in linea (2) rende solo T7 lavoro, e T6 fallire, che è quello che mi aspetterei come comportamento corretto.

Il mio attuale sospetto è che la chiamata a universe nella riga (1) sia stata valutata troppo presto. Ad esempio, il seguente diverge anche, mentre ci dovrebbe essere esattamente un valore nella lista, che non dovrebbe nemmeno essere valutati:

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

Quindi, l'unico caso, T8 (T8 (...) ...), viene valutato all'interno della lista , anche se non è necessario! Non ho idea di dove questo effetto provenga - è l'uso ricorsivo della sua istanza Universe? Ma perché, allora, i tipi "giusti ricorsivi" come T6 si comportano correttamente, mentre quelli "a sinistra ricorsivi" (T7) non lo fanno?

Si tratta di un problema di rigidità? Se sì, in quale parte del codice? La mia istanza Universe? Generic? E come ripararlo? Io uso GHC 7.6.3, se questo è importante.

Answer 1

Non è possibile generare tipi come T8. Diamo un'occhiata a ciò che la versione generici di universo per T8 riduce in realtà a:

t8Universe :: [T8] 
t8Universe = fmap T8 t8Universe 

In nessun momento è una (:) o [] prodotti. Senza un altro costruttore non ricorsivo per produrre con successo non c'è modo di fare progressi. t8Universe ha esattamente quanti elementi ha lo t8Universe, ma è circolare, e quindi loop di valutazione.