Как определить экземпляр NFData для рекурсивного одноэлементного типа?

Question

Я пользуюсь singletons библиотеки. У меня есть этот тип данных:

import Control.DeepSeq 
import Data.Singletons.Prelude 
import Data.Singletons.TH 

data T = 
     A 
    | B [T] 

genSingletons [''T] 

Я хочу генерируемый одноплодный тип ST быть экземпляром NFData. Было бы просто, если бы тип T не был бы рекурсивным. Я попытался написать это:

instance NFData (ST a) where 
    rnf SA =() 
    rnf (SB (x `SCons` xs)) = rnf x `seq` rnf xs 

, но это не будет работать на последней строке с сообщением:

Could not deduce (NFData (Sing n1)) arising from a use of `rnf' 
from the context (a ~ 'B n) 
    bound by a pattern with constructor 
      SB :: forall (z_azEs :: T) (n_azEt :: [T]). 
        (z_azEs ~ 'B n_azEt) => 
        Sing n_azEt -> Sing z_azEs, 
      in an equation for `rnf' 
or from (n ~ (n0 : n1)) 
    bound by a pattern with constructor 
      SCons :: forall (a0 :: BOX) (z0 :: [a0]) (n0 :: a0) (n1 :: [a0]). 
         (z0 ~ (n0 : n1)) => 
         Sing n0 -> Sing n1 -> Sing z0, 
      in an equation for `rnf' 
In the second argument of `seq', namely `rnf xs' 
In the expression: rnf x `seq` rnf xs 
In an equation for `rnf': 
    rnf (SB (x `SCons` xs)) = rnf x `seq` rnf xs 

Я понимаю, что GHC хочет x и xs в шаблоне SB (x ``SCons`` xs)) быть экземплярами NFData, но у меня есть проблема выяснить, как именно это сказать. Что я должен писать в контексте этого экземпляра, чтобы заставить его работать?

Answer 1

Во-первых, вам нужно предоставить NFData экземпляры для однотоновых списков.

instance NFData (SList '[]) where 
    rnf SNil =() 

instance (NFData (Sing x), NFData (SList xs)) => NFData (SList (x ': xs)) where 
    rnf (SCons x xs) = rnf x `seq` rnf xs 

Обратите внимание, что вы не можете решить эту проблему в одном экземпляре, потому что таким образом вы не могли обеспечить рекурсивные NFData ограничения:

instance NFData (SList xs) where 
    rnf SNil =() 
    rnf (SCons x xs) = ? -- no way to know if NFData (Sing x) 

Кроме того, вы должны писать отдельные экземпляры для T:

instance NFData (ST A) where 
    rnf SA =() 

instance NFData (SList xs) => NFData (ST (B xs)) where 
    rnf (SB xs) = rnf xs