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

问题描述

此博客文章有一个有趣的解释如何使用欧米茄monad对角线枚举任意语法。他提供了一个如何这样做的例子，导致了无限的字符串序列。我想这样做，除了生成一个字符串列表，而不是生成一个实际的数据类型列表。例如，

  data T = A | B T | CTT 
  

会生成

  A，BA，CAA，C（BA）A ... 
  

或相似的东西。不幸的是，我的Haskell技能还在成熟，经过几个小时的演奏，我无法做到自己想做的事。如何做到这一点？

按照要求，我的一个尝试（我尝试了太多东西......）：

  import Control.Monad.Omega 
 
 data T = A | B T | CTT派生（显示）
 
a = [A] 
 ++（do {x < -  each a; return（B x）}）
 ++（do {x <  -  each a; y<  -  each a; return（C xy）}）
 
 main = print $ take 10 $ a 
  

解决方案

我的第一个丑陋的方法是：

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

但是，经过一些清理后， p>

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

---

疯狂的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 
] 
  

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

Would generate

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

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]

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.

---

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屋！