[Haskell-cafe] Fair diagonals

[Luke Palmer]

On Fri, Nov 6, 2009 at 3:06 AM, Martijn van Steenbergen
<martijn at van.steenbergen.nl> wrote:
> "(...) Likewise, a breadth-first search of a data structure can fall short
> if it has an infinitely branching node. Omega addresses this problem by
> using a "diagonal" traversal that gracefully dissolves such data."
>
> However, I can't verify this:
>>
>>  runOmega . mapM each $ map (:[]) [1..]
>> *** Exception: stack overflow
>
> Or maybe I misunderstood Omega's documentation.

You are asking for the impossible.

>>> runOmega . mapM each $ [[1],[2],[3],[4],[5],[6]]
[[1,2,3,4,5,6]]

Replace one of them with the empty list
>>> runOmega . mapM each $ [[1],[2],[3],[],[5],[6]]
[]

If any of the lists is empty, the output will be empty.  So if you
give it an infinite number of lists, it cannot ever return any
information to you, since at some point in the future it may come
across an empty list.

Unless, of course, it *does* encounter an empty list, in which case it
knows the answer:

runOmega . mapM each $ map (:[]) [1..10] ++ [] ++ map (:[]) [12..]
[]

Luke