Infinite list in Haskell

Question

I'm trying to define a function that creates infinite list of all possible words in my simple grammar. But ghci freezes when I enter head (generate [] []), although head (generate' [] []) works fine (but I still want an infinite list). What's the problem?

data Start = Start deriving(Show)
data MyExpr = MyExprStart Start | MyExpr1 MyExpr | MyExpr2 MyExpr deriving(Show)

generate :: [MyExpr] -> [MyExpr] -> [MyExpr]
generate [] []         = generate [MyExprStart Start] []
generate current prev  = generate (concatMap nextExprs current) (prev ++ current)

generate' :: [MyExpr] -> [MyExpr] -> [MyExpr]
generate' [] []         = generate' [MyExprStart Start] []
generate' current prev  =
  if (length current + length prev) < 5 then
    generate' (concatMap nextExprs current) (prev ++ current)
  else prev ++ current

nextExprs :: MyExpr -> [MyExpr]
nextExprs expr = [MyExpr1 expr, MyExpr2 expr]

UPD: Thank you, I got the point. I think I should define my function like that:

generate :: [MyExpr] -> [MyExpr]
generate []         = generate [MyExprStart Start]
generate current    = current ++ generate (concatMap nextExprs current)

Fyodor Soikin · Accepted Answer · 2017-12-06T16:54:49.233

The generate function freezes, because it encodes an infinite recursion. Look: every case of it just calls the function itself. There is no condition when it actually returns something that is not a call to itself. So when you try to run it, it just keeps calling itself forever.

The generate' function, on the other hand, will bail out as soon at the combined length of two input lists exceeds 5. So that's when returns you a result.

To make this function start returning data before evaluating completely (which it can never do), you need to first return the non-recursive cases, and then append the recursive cases to them by calling generate recursively:

generate = (MyExprStart Start) : [recur e | e <- generate, recur <- [MyExpr1, MyExpr2]]

GHCi:

> head generate
MyExprStart Start
> take 10 generate
[MyExprStart Start, MyExpr1 (MyExprStart Start),
 MyExpr2 (MyExprStart Start), MyExpr1 (MyExpr1 (MyExprStart Start)),
 MyExpr2 (MyExpr1 (MyExprStart Start)),
 MyExpr1 (MyExpr2 (MyExprStart Start)),
 MyExpr2 (MyExpr2 (MyExprStart Start)),
 MyExpr1 (MyExpr1 (MyExpr1 (MyExprStart Start))), 
 MyExpr2 (MyExpr1 (MyExpr1 (MyExprStart Start))),
 MyExpr1 (MyExpr2 (MyExpr1 (MyExprStart Start)))]

NOTE: the order of generators in the list comprehension is important. If you swap them, the execution will never get to MyExpr2, because it would need to exhaust the generate list first, and that list is infinite.

chi · Answer 2 · 2017-12-06T16:44:35.263

generate :: [MyExpr] -> [MyExpr] -> [MyExpr]
generate ... = generate ...
generate ... = generate ...

Any definition of this form will always call itself before producing any output. This kind of inductive structure can be defined only if, at least at some point, it returns some part of the output before recursing, e.g. emitting the first element of the output list.

generate' :: [MyExpr] -> [MyExpr] -> [MyExpr]
generate' [] []         = generate' [MyExprStart Start] []
generate' current prev  =
  if (length current + length prev) < 5 then
    generate' (concatMap nextExprs current) (prev ++ current)
  else prev ++ current

By comparison, in generate' the else branch does not recurse, so it will produce the output. Even if we had something like

else someNonEmptyList ++ generate' ...

this would work, since the first few list elements would be produced.

Further, keep in mind that generating all the possible expressions merging potentially infinite lists with ++ is a bad idea. Indeed, if xs is infinite then xs ++ ys is equal to xs, since ys will never be reached in finite time. You probably want a fair interleaving of xs and ys when they are infinite.

A similar question used the omega monad to achieve the complete enumeration.

Infinite list in Haskell

2 Answers2