Compute an infinite list of all finite Blurgs

Question

Suppose we define the following datatype in Haskell:

data Blurg = Blub
           | Zarg
           | Parg Blurg Blurg

This means that Zarg, Parg Blub (Parg Zarg Zarg), Parg (Parg Blub Blub) (Parg Blub Blub), etc., are all examples of Blurgs.

Now an old exam question is as follows:

Define a function which will compute a list of all Blurgs.

So I tried:

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

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

At first I thought this was a solution, but then I realized that not all possible Blurgs are included in the resulting list allBlurg. Can someone write a proper solution?

By the way, I'd just like to note that what the problem asks for won't really be a function since it doesn't take any arguments; it should be considered a value instead. Second, although the question doesn't explicitly say so, I think it should be a condition that each Blurg only appears once in the list. Also please note that the problem really should only ask for finite Blurgs as user zch has mentioned in the comments.

I think it's not possible. There is uncountable number of binary trees. Your method generates all finite Blurgs, but there is no way to fit all infinite Blurgs into a list. — zch, Apr 04 '15 at 12:39
Another problem is that most Blurgs are actually uncomputable, so there is no way to define them in Haskell. — zch, Apr 04 '15 at 12:48
@zch: I think there is an infinite but countable number of binary trees, but either way I don't think that it is relevant here. At any rate, think about the question like this: if you give me an arbitrary Blurg, it should be contained in the list. — Sid, Apr 04 '15 at 12:51
there is countable number of finite binary trees (and your function generate all of them, including your example), but number of infinite trees is uncountable. You could easily encode digits of a real number on an infinite branch of binary tree. This means that there is no one-to-one function from Blurgs into natural numbers. Likewise, you could contain solution of halting problem on an infinite branch. — zch, Apr 04 '15 at 13:02
@zch: I take it the task was meant as “compute a list of all _finite_ `Blurg`s”. — leftaroundabout, Apr 04 '15 at 13:03
@zch: It's good that you bring this up because I felt like it was clear by context that the problem was only about finite Blurgs - as you said, most infinite Blurgs wouldn't even be computable. I'll update the question so that this is clear, thanks for the note. But I don't think it's true that my list will contain the example I gave above, the Blurgs "Blub" and "Parg (Parg Blub Blub) Blub" will never be together in the list "sofar" at the same recursive call. — Sid, Apr 04 '15 at 13:14
Potential duplicate of http://stackoverflow.com/questions/23515191/how-to-enumerate-a-recursive-datatype-in-haskell — chi, Apr 04 '15 at 13:17
@chi: While a similar problem, it does not look like a duplicate to me. — Sid, Apr 04 '15 at 13:22
The difference is very thin, in my opinion: the other question asked explicitly how to do that using the Omega monad, while this question asks about how to do it in general. The only other minor difference is that they have a slightly different recursive type. — chi, Apr 04 '15 at 13:31
chi: For me those differences are substantial: I am not especially interested in seeing how to solve this problem with a library function since I won't have access to those when I need to solve similar problems on an upcoming exam, which is why I asked for a general solution. And that the other problem uses a different recursive type makes it, well, a different problem. But it's still useful to see that link, thanks. — Sid, Apr 04 '15 at 13:53

leftaroundabout · Answer 1 · 2015-04-04T13:02:39.547

Basically, we need this list:

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

Well, actually you can write this out just like that in Haskell:

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

BTW this is not a function, though the definition is recursive. In Haskell, values can be recursive!

Perhaps the above is actually what was expected in the task. Trouble is, it's actually wrong: not all Blurg values will be contained! The reason being, y<-allBlurg has to work through an infinite list. It will never get to the end, therefore x will stay forever at the first element. I.e., with that “solution”, you'll actually only get lists of the form

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

but never Pargs x y with some x apart from Blub.

What's needed to solve this problem: enumerate combinations from two infinite lists. That's the Cantor pairing function, a Haskell implementation is available here.

{-# 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 x y | x <‌- each allG, y <‌- each allG ]
GHCi> take 100 allG
[B, Z, P B B, P B Z, P Z B, P B (P B B), P Z Z, P (P B B) B,
P B (P B Z), P Z (P B B), P (P B B) Z, P (P B Z) B, P B (P Z B),
P Z (P B Z), P (P B B) (P B B), P (P B Z) Z, P (P Z B) B,
P B (P B (P B B)), P Z (P Z B), P (P B B) (P B Z), P (P B Z) (P B B),
P (P Z B) Z, P (P B (P B B)) B, P B (P Z Z), P Z (P B (P B B)),
P (P B B) (P Z B), P (P B Z) (P B Z), P (P Z B) (P B B),
P (P B (P B B)) Z, P (P Z Z) B, P B (P (P B B) B), P Z (P Z Z),
P (P B B) (P B (P B B)), P (P B Z) (P Z B), P (P Z B) (P B Z),
P (P B (P B B)) (P B B), P (P Z Z) Z, P (P (P B B) B) B,
P B (P B (P B Z)), P Z (P (P B B) B), P (P B B) (P Z Z),
P (P B Z) (P B (P B B)), P (P Z B) (P Z B), P (P B (P B B)) (P B Z),
P (P Z Z) (P B B), P (P (P B B) B) Z, P (P B (P B Z)) B,
P B (P Z (P B B)), P Z (P B (P B Z)), P (P B B) (P (P B B) B),
P (P B Z) (P Z Z), P (P Z B) (P B (P B B)), P (P B (P B B)) (P Z B),
P (P Z Z) (P B Z), P (P (P B B) B) (P B B), P (P B (P B Z)) Z,
P (P Z (P B B)) B, P B (P (P B B) Z), P Z (P Z (P B B)),
P (P B B) (P B (P B Z)), P (P B Z) (P (P B B) B), P (P Z B) (P Z Z),
P (P B (P B B)) (P B (P B B)), P (P Z Z) (P Z B),
P (P (P B B) B) (P B Z), P (P B (P B Z)) (P B B), P (P Z (P B B)) Z,
P (P (P B B) Z) B, P B (P (P B Z) B), P Z (P (P B B) Z),
P (P B B) (P Z (P B B)), P (P B Z) (P B (P B Z)),
P (P Z B) (P (P B B) B), P (P B (P B B)) (P Z Z),
P (P Z Z) (P B (P B B)), P (P (P B B) B) (P Z B),
P (P B (P B Z)) (P B Z), P (P Z (P B B)) (P B B), P (P (P B B) Z) Z,
P (P (P B Z) B) B, P B (P B (P Z B)), P Z (P (P B Z) B),
P (P B B) (P (P B B) Z), P (P B Z) (P Z (P B B)),
P (P Z B) (P B (P B Z)), P (P B (P B B)) (P (P B B) B),
P (P Z Z) (P Z Z), P (P (P B B) B) (P B (P B B)),
P (P B (P B Z)) (P Z B), P (P Z (P B B)) (P B Z),
P (P (P B B) Z) (P B B), P (P (P B Z) B) Z, P (P B (P Z B)) B,
P B (P Z (P B Z)), P Z (P B (P Z B)), P (P B B) (P (P B Z) B),
P (P B Z) (P (P B B) Z), P (P Z B) (P Z (P B B)),
P (P B (P B B)) (P B (P B Z)), P (P Z Z) (P (P B B) B)]

Now, actually this is still incomplete: it's actually just the list of all finite-depth Blurgs. As zch remarks, most Blurgs are uncomputable, there's no chance to actually enumerate all of them.

Thanks for the solution. But my compiler cannot parse the word `each`, are you sure you meant to have that there? — Sid, Apr 04 '15 at 13:17
`each` is just another function, defined in the `Control.Monad.Omega` module. — leftaroundabout, Apr 04 '15 at 13:19
I'm not a fan of mixing omega and lists in that way. I'd rather keep everything inside omega as much as possible and escaping from that at the end. You can also use `Alternative` as in http://stackoverflow.com/questions/23515191/how-to-enumerate-a-recursive-datatype-in-haskell — chi, Apr 04 '15 at 13:20
@chi: I kinda agree about better staying with the same container, however in this case it's not really a problem – at least performance-wise, because `Omega` is in fact nothing but a newtype wrapper around a list. And IMO, the combination of monad comprehension and `each` is actually extremely readable and intuitive. — leftaroundabout, Apr 04 '15 at 13:40

score 2 · Accepted Answer · answered Apr 04 '15 at 14:19

As @leftaroundabout explained the problem - in your solution x never matches anything beyond the first element, because y has infinite number of elements to match.

Here is more elementary solution to this problem:

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]

To avoid problem with infinite iteration I use lists with trees of various depths.

nextDepth takes a list of trees with depth < n and list of trees of depth == n and returns trees of depth == n + 1 that can be constructed from them.

deeper for similar arguments returns trees of depth >= n (except for infinite ones).

score 0 · Answer 3 · answered Apr 23 '15 at 04:03

You can also use this approach: start with a leaf node and a function that expands one leaf node into a tree. The code I'm about to include is a slight variation but the same basic idea.

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]

Compute an infinite list of all finite Blurgs

3 Answers3