How to enumerate values of user-defined data types?

[johannes-riecken]

I'm having trouble implementing the example from the paper about enumerating Family. The package mentions a Math.Combinatorics.Species.TH module, which doesn't exist.

With my below approach I get the error

/private/tmp/example.hs:13:10: error: [GHC-39999] • No instance for ‘Typeable (StructTy Family)’ arising from the superclasses of an instance declaration • In the instance declaration for ‘Enumerable Family’ | 13 | instance Enumerable Family | ^^^^^^^^^^^^^^^^^

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE TypeFamilies #-}
import Data.Typeable
import GHC.Generics (Generic, Generic1)
import Math.Combinatorics.Species
import NumericPrelude

data Family a = Monkey Bool a | Group a [Family a]
    deriving (Generic, Generic1, Show)

instance Enumerable Family

main :: IO ()
main = do
    let fam = fromInteger 2 * x + x * (linOrds `o` fam)
    print (enumerate fam [1,2] :: [Family Int])

[byorgey]

Unfortunately, the Math.Combinatorics.Species.TH module was removed in 2016, when there were breaking changes in template-haskell and I didn't have the energy to figure out how to fix it. In theory you could declare all the necessary instances and type family definitions yourself, but it is tricky and nonobvious how to do so. In particular, your recursive definition of fam will not work; recursive species cannot be defined directly using Haskell recursion because we need to be able to reify them as (non-infinite) fixpoint expressions. So there is a level of indirection needed. I spent the past 45 minutes staring at the old TH code and trying to figure out how to declare the necessary instances. In the end I got something that typechecked but then generated garbage, so clearly I did something wrong. For posterity's sake, here was my attempt:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE TypeFamilies #-}
import Data.Typeable
import GHC.Generics (Generic, Generic1)
import Math.Combinatorics.Species
import Math.Combinatorics.Species.Structures
import Math.Combinatorics.Species.AST
import NumericPrelude

data Family a = Monkey Bool a | Group a [Family a]
    deriving (Generic, Generic1, Show)

data FamilyC = FamilyC deriving Show

type instance Interp FamilyC self = (Const Integer :*: Id) :+: (Id :*: ([] :.: self))

instance ASTFunctor FamilyC where
  apply _ self = unwrap (fromInteger 2 * x + x * (linOrd @@ wrap self))

instance Enumerable Family where
  type StructTy Family = Mu FamilyC
  iso (Mu (Inl (Const b :*: Id a))) = Monkey (case b of {1 -> False; 2 -> True}) a
  iso (Mu (Inr (Id a :*: Comp ms))) = Group a (map iso ms)

fam :: Species s => s
fam = rec FamilyC

main :: IO ()
main = do
    print (enumerate fam [1,2] :: [Family Int])

[johannes-riecken]

Hmm, thanks for the effort so far. Do you still have anyone you could ask about this? Or otherwise we could ask the Haskell community on Reddit? I saw your paper and slides both mentioned test data generator as the main selling point of the library, so it would be cool to get this working again, though I sadly don't know enough about this.

[byorgey]

I doubt asking anyone else is going to help, since the most difficult part is just understanding how the library is put together, what instances are needed, and why; and I'm still the person who understands that part the best.

If you want to do test data generation, there are much better alternatives; for example, I would recommend looking into https://hackage.haskell.org/package/dragen .