[Haskell-cafe] Fair diagonals

Martijn van Steenbergen martijn at van.steenbergen.nl
Fri Nov 6 05:06:33 EST 2009


Henning Thielemann wrote:
> 
> On Wed, 4 Nov 2009, Sjoerd Visscher wrote:
> 
>>
>> On Nov 4, 2009, at 3:21 PM, Twan van Laarhoven wrote:
>>
>>       I looked on hackage but I was surprised that I couldn't find 
>> this simple
>>       monad. The package level-monad does look very similar, only it 
>> uses a
>>       different list type for the representation.
>>
>>
>> indeed, level-monad works as well:
>>
>> import Control.Monad.Levels
>> import Data.FMList (fromList)
>>
>> diagN = bfs . mapM fromList
> 
> Can someone explain the difference between control-monad-omega and 
> level-monad?

So from what I understand this is the difference:

Omega is biased towards the lower dimensions while Levels
treats all dimensions equally, or at least more equally. You can 
formalize the latter by saying: the sums of the indices should be 
non-decreasing.

 From Omega's documentation I understand this is on purpose:

"(...) 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.

Martijn.


More information about the Haskell-Cafe mailing list