Sjoerd Visscher wrote:
I believe this does what you want:
<code>
The attached code should be more efficient, since it doesn't use integer
indices.
Note that this is just a 'level' monad: the list is stratified into levels, when
combining two levels, the level of the result is the sum of the levels of the
inputs.
map (map sum) . runDiags . traverse each $ [[1..], [1..], [1..]]
[[3],[4,4,4],[5,5,5,5,5,5],[6,6,6,6,6,6,6,6,6,6],[7,7,7,7,7,7,7,7,7,7,7,...
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.
By the way, it seems Omega intentionally doesn't use this design. To quote the
documentation "... a breadth-first search of a data structure can fall short if
it has an infinitely branching node. Omega addresses this problem ..."
Twan
-- A simple 'level' monad type
module MonadDiags where
import Control.Applicative
import Control.Monad
apD :: [[a -> b]] -> [[a]] -> [[b]]
apD [] _ = []
apD _ [] = []
apD (xx:xs) ys = unionD (map apXX ys) ([] : apD xs ys)
where apXX yy = xx <*> yy
unionD :: [[a]] -> [[a]] -> [[a]]
unionD [] ys = ys
unionD xs [] = xs
unionD (x:xs) (y:ys) = (x++y) : unionD xs ys
-- Now to wrap things up in an applicative functor
newtype Diags a = Diags { runDiags :: [[a]] }
instance Functor Diags where
fmap f = Diags . map (map f) . runDiags
instance Applicative Diags where
pure a = Diags [[a]]
a <*> b = Diags (runDiags a `apD` runDiags b)
instance Alternative Diags where
empty = Diags [[]]
a <|> b = Diags (runDiags a `unionD` runDiags b)
each :: [a] -> Diags a
each = Diags . map return
-- And if we want a monad, we should also have a join function
joinD :: [[Diags a]] -> [[a]]
joinD [] = []
joinD (xx:xs) = unionsD (map runDiags xx) `unionD` ([] : joinD xs)
unionsD :: [[[a]]] -> [[a]]
unionsD = foldr unionD []
instance Monad Diags where
return = pure
a >>= b = Diags (joinD (runDiags $ fmap b a))
fail _ = empty
instance MonadPlus Diags where
mzero = empty
mplus = (<|>)
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
