如何在 Haskell 中枚举递归数据类型? [英] How to enumerate a recursive datatype in Haskell?

问题描述

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

This blog post has an interesting explanation of how to use the Omega monad to enumerate an arbitrary grammar diagonally. He offers an example of how to do so, resulting in an infinite sequence of strings. I'd like to do the same, except that, instead of generating a list of strings, it generates a list of an actual datatype. For example,

 data T = A | B T | C T T

会产生

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

或类似的东西.不幸的是，我的 Haskell 技能仍在成熟，在玩了几个小时后，我无法做我想做的事.怎么做?

Or something similar. Unfortunately my Haskell skills are still maturing and after some hours playing it I couldn't manage to do what I want. How can that be done?

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

As requested, one of my attempts (I have tried too many things...):

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

推荐答案

我第一个丑陋的方法是:

My first ugly approach was:

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

但是，经过一番清理后，我到达了这个班轮

But then, after some cleaning up I reached this one liner

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

Note that order matters: return A has to be the first choice in the list above, or allTerms will not terminate. Basically, the Omega monad ensures a "fair scheduling" among choices, saving you from e.g. infiniteList ++ something, but does not prevent infinite recursion.

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

An even more elegant solution was suggested by Crazy FIZRUK, exploiting the Alternative instance of Omega.

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

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

这篇关于如何在 Haskell 中枚举递归数据类型?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！