计算所有有限Blurgs的无限列表

Question

假设我们在Haskell中定义了以下数据类型:

data Blurg = Blub
           | Zarg
           | Parg Blurg Blurg

这意味着Zarg,Parg Blub (Parg Zarg Zarg),Parg (Parg Blub Blub) (Parg Blub Blub)等,是所有实例Blurgs.

现在一个旧的考试问题如下:

定义一个函数,它将计算所有Blurgs的列表.

所以我尝试过:

allBlurg' :: [Blurg] -> [Blurg]
allBlurg' sofar = sofar ++ allBlurg' [Parg x y | x <- sofar, y <- sofar]

allBlurg :: [Blurg]
allBlurg = allBlurg' [Blub, Zarg]

起初我认为这是一个解决方案,但后来我意识到并非所有可能的Blurgs都包含在结果列表中allBlurg.有人能写一个合适的解决方案吗

顺便说一句,我只想指出,问题所要求的并不是真正的功能,因为它不需要任何参数; 它应该被视为一个价值.其次,虽然问题没有明确说明,但我认为这应该是每个Blurg只在列表中出现一次的条件.另请注意,问题实际上应该只是询问用户zch在评论中提到的有限Blurgs.

Answer 1

基本上,我们需要这个列表:

Blub : Zarg : [ Parg x y | {- `x`,`y` from all possible `Blurg` values -} ]

好吧,实际上你可以像在Haskell中那样写出来:

allBlurg :: [Blurg]
allBlurg = Blub : Zarg : [ Pargs x y | x<-allBlurg, y<-allBlurg ]

顺便说一句,这不是一个函数,尽管定义是递归的.在Haskell中,值可以递归!

也许以上实际上是在任务中所期望的.麻烦的是,它实际上是错误的:并非所有的Blurg值都会被包含!原因是,y<-allBlurg必须通过一个无限的列表.它永远不会结束,因此x将永远留在第一个元素.即,通过该"解决方案",您实际上只能获得表单的列表

   Pargs Blub . Pargs Blub . Pargs Blub . Pargs Blub ... Pargs Blub $ x

但从来没有Pargs x y与一些人x分开Blub.

解决此问题需要什么:枚举来自两个无限列表的组合.这是Cantor配对功能,这里有Haskell实现.

{-# LANGUAGE MonadComprehensions #-}
import Control.Monad.Omega

allBlurg :: [Blurg]
allBlurg = Blub : Zarg : runOmega [ Pargs x y | x <- each allBlurg
                                              , y <- each allBlurg ]

GHCi>:set -XMonadComprehensions
GHCi>:m + Control.Monad.Omega
GHCi> let allG = B:Z:runOmega [P xy | x < - 每个allG,y < - 每个allG]
GHCi>取100个allG
    [B,Z,PBB,PBZ,PZB,PB(PBB),PZZ,P(PBB)B,
    PB(PBZ),PZ( PBB),P(PBB)Z,P(PBZ)B,PB(PZB),
    PZ(PBZ),P(PBB)(PBB),P(PBZ)Z,P(PZB)B,
    PB(PB(PBB) )),PZ(PZB),P(PBB)(PBZ),P(PBZ)(PBB),
    P(PZB)Z,P(PB(PBB))B,PB(PZZ),PZ(PB(PBB) ),
    P(PBB)(PZB),P(PBZ)(PBZ),P(PZB)(PBB),
    P(PB(PBB))Z,P(PZZ)B,PB(P(PBB)B), PZ(PZZ),
    P(PBB)(PB(PBB)),P(PBZ)(PZB),P(PZB)(PBZ),
    P(PB(PBB))(PBB),P(PZZ)Z,P (P(PBB)B)B,
    PB(PB(PBZ)),PZ(P(PBB)B),P(PBB)(PZZ),
    P(PBZ)(PB(PBB)),P(PZB)( PZB),P(PB(PBB))(PBZ),
    P(PZZ)(PBB),P(P(PBB)B)Z,P(PB(PBZ))B,
    PB(PZ(PBB)),PZ (PB(PBZ)),P(PBB)(P(PBB)B),
    P(PBZ)(PZZ),P(PZB)(PB(PBB)),P(PB(PBB))(PZB),
    P (PZZ)(PBZ),P(P(PBB)B)(PBB),P(PB(PBZ))Z,
    P(PZ(PBB))B,PB(P(PBB)Z),PZ(PZ(PZ) PBB)),
    P(PBB)(PB(PBZ)),P(PBZ)(P(PBB)B),P(PZB)(PZZ),
    P(PB(PBB))(PB(PBB)),P (PZZ)(PZB),
    P(P(PBB)B)(PBZ),P(PB(PBZ))(PBB),P(PZ(PBB))Z,
    P(P(PBB)Z)B,PB(P(PBZ)B),PZ(P(PBB)Z),
    P(PBB)(PZ(PBB)),P( PBZ)(PB(PBZ)),
    P(PZB)(P(PBB)B),P(PB(PBB))(PZZ),
    P(PZZ)(PB(PBB)),P(P(PBB)B )(PZB),
    P(PB(PBZ))(PBZ),P(PZ(PBB))(PBB),P(P(PBB)Z)Z,
    P(P(PBZ)B)B,PB(PB (PZB)),PZ(P(PBZ)B),
    P(PBB)(P(PBB)Z),P(PBZ)(PZ(PBB)),
    P(PZB)(PB(PBZ)),P( PB(PBB))(P(PBB)B),
    P(PZZ)(PZZ),P(P(PBB)B)(PB(PBB)),
    P(PB(PBZ))(PZB),P(PZ) (PBB))(PBZ),
    P(P(PBB)Z)(PBB),P(P(PBZ)B)Z,P(PB(PZB))B,
    PB(PZ(PBZ)),PZ(PB (PZB)),P(PBB)(P(PBZ)B),
    P(PBZ)(P(PBB)Z),P(PZB)(PZ(PBB)),
    P(PB(PBB))(PB( PBZ)),P(PZZ)(P(PBB)B)]

现在,实际上这仍然是不完整的:它实际上只是所有有限深度 的列表Blurgs.正如zch所说,大多数Blurgs是不可计算的,没有机会实际枚举所有这些.