1

Suppose we have the following grammar:

#x = INT | (#x + #x)
INT = 0 | 1

Suppose now I would like to make an infinite stream that "contains" every possible form of #x.

Here's what I can think of so far: 

atomic :: [String]
atomic = ["0", "1"]
--------------------
plus :: String -> String -> String
plus x1 x2 = "(" ++ x1 ++ "+" ++ x2 ++ ")"
--------------------
makeInfiniteStream :: [String]
makeInfiniteStream = atomic : --something

I'm not quite sure what goes on the other other side of the colon. I assume it has to involve a function call, but I don't quite see it yet.

Thanks.

HoopsMcCann
  • 347
  • 2
  • 3
  • 18
  • 1
    I think this is an almost-duplicate of [this question](https://stackoverflow.com/questions/23515191/how-to-enumerate-a-recursive-datatype-in-haskell). Using strings or an ADT makes no significant difference. (I'm waiting a bit to mark this as a duplicate since my vote would close this instantly.) – chi Oct 26 '18 at 16:35
  • Note there's a simple answer that is technically correct, but fails to generate certain elements in a finite number of steps. `makeInfiniteStream = atomic ++ [plus x y | x <- makeInfiniteStream, y <- makeInfiniteStream]`. (Posting as a comment because it's not really useful in practice.) – chepner Oct 26 '18 at 16:55
  • Besides @chi's proposed dupe, see [this related question](https://stackoverflow.com/q/23923229/791604) from the same asker. (It assumes the step of enumerating terms is too easy and asks you to give an efficient way to jump around in that list.) – Daniel Wagner Oct 26 '18 at 17:10
  • [related](https://cs.stackexchange.com/questions/97539/lambda-calculus-generator/97610#97610). it diagonalizes the product. ( @chepner ) – Will Ness Oct 26 '18 at 17:44

0 Answers0