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

Question

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

Answer 1

我的第一个丑陋方法是:

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++ some，但不阻止无限递归。

<小时/>

Crazy FIZRUK 提出了一个更优雅的解决方案。 ，利用 Omega 的替代实例。

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

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