[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