9

私の別の答えとして、列挙可能な s の斜めにトラバースされたインスタンスを提供する次のコードを作成しました（ UniverseそこGenericのバージョンからわずかに更新されていますが、同じロジックを使用しています）：

{-# 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)いくだけで失敗するというのが正しい動作だと思います。T7T6

私の現在の疑いは、universein lineへの呼び出しの(1)評価が早すぎることです。たとえば、次の例も発散しますが、リストには値が1 つだけある必要があり、評価する必要さえありません。

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

したがって、唯一のインスタンス は、必要ではありませんが、 list 内でT8 (T8 (...) ... )評価されます! この効果がどこから来ているのかわからない - それはそれ自身のインスタンスの再帰的な使用ですか? しかし、なぜ「右再帰」型は正しく動作し、「左再帰」型 ( ) は正しく動作しないのでしょうか?UniverseT6T7

これは厳しさの問題ですか？もしそうなら、コードのどの部分ですか？私のUniverseインスタンス？Generic? そして、それを修正する方法は？それが問題なら、GHC 7.6.3を使用します。

4

1 に答える 1

0

のような型T8は生成できません。T8 のユニバースのジェネリック バージョンが実際に何に還元されるかを見てみましょう。

t8Universe :: [T8]
t8Universe = fmap T8 t8Universe

(:) または [] が生成されることはありません。別の非再帰コンストラクターが正常に生成されなければ、進歩する方法はありません。t8Universeとまったく同じ数の要素がt8Universeありますが、それは循環的であるため、評価がループします。

于 2015-09-07T20:55:23.150 に答える