haskell - 如何枚举Haskell中的递归数据类型？

This blog post对如何使用Omega monad对角枚举任意语法有一个有趣的解释。他提供了一个示例，说明了如何执行此操作，从而产生了无限的字符串序列。我想做同样的事情，除了它不是生成字符串列表，而是生成实际数据类型的列表。例如，

 data T = A | B T | C T T

会产生

A, B A, C A A, C (B A) A...

或类似的东西。不幸的是，我的Haskell技能仍在成熟，玩了几个小时后，我没办法做我想做的事。那怎么办？

根据要求，我的尝试之一(我尝试了太多事情...):

import Control.Monad.Omega

data T = A | B T | C T T deriving (Show)

a = [A]
        ++ (do { x <- each a; return (B x) })
        ++ (do { x <- each a; y <- each a; return (C x y) })

main = print $ take 10 $ a

最佳答案

我的第一个丑陋方法是:

allTerms :: Omega T
allTerms = do
  which <- each [ 1,2,3 ]
  if which == 1 then
    return A
  else if which == 2 then do
    x <- allTerms
    return $ B x
  else do
    x <- allTerms
    y <- allTerms
    return $ C x y

但是然后，经过一番清理，我到达了这只内胆

import Control.Applicative
import Control.Monad.Omega
import Control.Monad

allTerms :: Omega T
allTerms = join $ each [return A, B <$> allTerms, C <$> allTerms <*> allTerms]

请注意顺序很重要:return A必须是上面列表中的首选，否则allTerms不会终止。基本上，Omega monad可以确保选择之间的“合理安排”，例如， infiniteList ++ something，但不阻止无限递归。

Crazy FIZRUK提出了一个更为优雅的解决方案，该方法利用了Alternative的Omega实例。

import Control.Applicative
import Data.Foldable (asum)
import Control.Monad.Omega

allTerms :: Omega T
allTerms = asum [ pure A
                , B <$> allTerms
                , C <$> allTerms <*> allTerms
                ]

omega

haskell - 如何枚举Haskell中的递归数据类型？