計算所有有限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

由於@leftaroundabout解釋了這個問題 - 在你的解決方案中x永遠不會匹配第一個元素以外的任何東西，因爲y有無數個要匹配的元素。

這裏是更基本的解決了這個問題：

nextDepth :: [Blurg] -> [Blurg] -> [Blurg] 
nextDepth ls ms = 
    [Parg x y | x <- ls, y <- ms] ++ 
    [Parg x y | x <- ms, y <- ls ++ ms] 

deeper :: [Blurg] -> [Blurg] -> [Blurg] 
deeper ls ms = ms ++ deeper (ls ++ ms) (nextDepth ls ms) 

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

爲了避免無限重複我用列表包含各種深度的樹木問題。

nextDepth需要的樹列表以及深度< n和深度== n樹列表並返回深度== n + 1可以從他們構造的樹。

deeper對於相似的參數返回深度爲>= n的樹（除了無限的樹）。

Answer 2

基本上，我們需要這個名單：

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從Blub一些x分開。

解決此問題需要什麼：列舉來自兩個無限列表的組合。這是Cantor pairing function，Haskell實現可用here。

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

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

GHCI>：組-XMonadComprehensions
GHCI>：M + Control.Monad。Omega
GHCi> let allG = B：Z：runOmega [P x y | X < - 每個ALLG，Y < - 每個ALLG]
GHCI>取100 ALLG
[B，Z，PBB，PBZ，PZB，PB（PBB），PZZ，P（PBB）B，
PB （PBZ），PZ（PBB），P（PBB），P（PBZ）Z，P（PZB），P（PBB）Z，P（PBZ）B，PB（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） （PBB）），P（PBZ）（PZB），P（PBB））Z，P（PZZ）B，PB（P（PBB）B），PZ（PZZ） P（PBZ）），P（PZB）（PBZ），
PB（PB（PBB）），P（PZZ）Z，P（P（PBB）B）B，
PB P（PBB）B）P（PBB）PZZ
P（PBZ）（PB（PBB）），P（PZB）（PZB），P（PB（PBB））（PBZ），
P （PZ（PBB）），P（P（PBB）），P（PBB）B）Z，P（PB（PBZ））B，
PB （PBB）B），
P（PBZ）（PZZ），P（PZB）（PB（PBB）），P（PB（PBB））（PZB），（PZ（PBB））B，PB（P（PBB）Z）P（PZZ）（PBZ），P（P（PBB）B）（PBB），P（PB（PBZ））Z， （PBB），PZ（PZ（PBB）），
P（PBB）（PB（PBZ）），P（PBZ）（P（PBB）B），P（PZB）（PZZ），
P ）（P（PBB）B）（PBZ），P（PB（PBZ）），（PBB），P（PZZ）（PZB），
Z P（PBB）），P（PBZ）Z）B，PB（P（PBZ）B），PZ（P（PBB）Z）
P（PBB） PBZ）），
P（PZB）（P（PBB）B），P（PB（PBB））（PZZ），（PBZ））（PBZ），P（PZ（PBB））（PBB），P（PBZ））（PBB），P（PZB） P（PBB）Z）
P ）P（PBZ）（PZ（PBB）），
P（PZZ）（PZZ）P（PBZ） ，P（P（PBB）B）（PB（PBB）），
P（PB（PBB））（PZB），P（PZ（PBB））（PBZ），
P （PBB），P（P（PBZ）B）Z，P（PB（PZB））B，
（PBZ）Z），P（PZB）（PZ（PBZ）），PZ（PBZ）），P（PBB）（P（PBZ）B），P（PBZ） PBB）），
P（PB（PBB））（PB（PBZ）），P（PZZ）（P（PBB），B）]

現在，其實這是仍然不完整的：它是實際上只是所有的有限深度的列表Blurgs。正如zch所言，絕大多數Blurg都不具備可靠性，所以沒有機會真正列舉出其中的全部。

Answer 3

您也可以使用這種方法：從一個葉節點和一個將一個葉節點擴展爲樹的函數開始。我將要加入的代碼只是一個小小的變化，但卻是相同的基本想法。

allBlurgs = ab [Blub] where 
    ab (a:r) = a : (r ++ expand a) 
    expand Blub = [Zarg, Parg Blub Blub] 
    expand Zarg = [] 
    expand (Parg a b) = [Parg a' b | a' <- expand a] ++ [Parg a b' | b' <- expand b]