无限递归枚举泛型实例

Question

对于我的another answer的所有值的时候，我写了下面的代码，提供diagonally traversedUniverse实例为枚举Generic S（它轻微地从这个版本有更新，但使用相同的逻辑）：

{-# 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可能是不相关的问题，但这个问题的一部分。）

这适用于大多数类型，甚至递归的像那些：

个

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) 

例子：

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

但是请注意，以上类型都不能在首位他们的递归构造！其实（这是问题），以下发散：

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

我首先想到的，也许有一些与Omegas的评估顺序，但交换左部和右部的线(2)不仅使T7工作，和T6失败，这正是我期望的正确行为。

我目前的怀疑是对universe行(1)的呼叫评估得太早。例如，下面还发散，而应该是在列表中，这甚至不应该被评估究竟一个值：

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

所以，唯一实例，T8 (T8 (...) ...)，获取评估列表内，即使它不需要！我不知道这个效应是从哪里来的 - 是它自己的Universe实例的递归使用？但是，为什么像T6这样的“正确的递归”类型行为正确，而“左递归”类型（T7）却不行？

这是一个严格的问题？如果是这样，哪部分代码？我的Universe实例？ Generic？以及如何解决它？如果有问题，我使用GHC 7.6.3。

Answer 1

类似T8不能生成这个。让我们来看看什么T8的仿制药版本的宇宙实际上降低到：

t8Universe :: [T8] 
t8Universe = fmap T8 t8Universe 

在任何时候，是[]生产（:)或。如果没有另一个非递归构造函数来成功产生，就没有办法取得进展。 t8Universe具有与t8Universe一样多的元素，但这是循环的，因此评估循环。