[Haskell-cafe] Monad transformers [Stacking monads]

[Reid Barton]

Hi Andrew,

On Mon, Oct 06, 2008 at 09:48:51PM +0100, Andrew Coppin wrote:
> data ResultSet x = Pack {unpack :: [[x]]} deriving (Eq)

Your ResultSet monad is roughly equivalent to

newtype Nat = Nat Int
instance Monoid Nat where
  mempty = Nat 0
  (Nat x) `mappend` (Nat y) = Nat (x+y)
type ResultSet' = WriterT Nat []
-- ResultSet' x = [(x, Nat)]

where unpack :: ResultSet' x -> [[x]] gives a list whose nth element
is the list of alternatives whose "cost" (Nat data) is n (with
trailing [] lists removed).  Except that using [[x]] internally lets
you be lazy about handling items of high cost.  (This is kind of neat
actually.)

I'd therefore guess that if there is an associated monad transformer
ResultSetT, it's similarly equivalent to

ResultSetT' m x = WriterT Nat (ListT m x)

where ListT is some version of "ListT done right".  But on the other
hand, as I understand "ListT done right", you can think of ListT m x
as a "list" of xs where you have to perform an action in the m monad
to get each successive value in the list.  The equivalence converting
ResultSet' to ResultSet sort of "tears up" the list in a way I'm not
sure is compatible with inserting a monad like that.


Once again, all this high-falutin' nonsense corresponds to really
concrete questions about what you want your code to *actually do*.
Consider your original problem

>  run :: State -> Foo -> Either ErrorType (ResultSet State)
>
>  run_and :: State -> Foo -> Foo -> Either ErrorType (ResultSet State)
>  {- some Either-ified version of
>     run_and :: State -> Foo -> Foo -> ResultSet State
>     run_and s0 x y = do
>       s1 <- run s0 x
>       s2 <- run s1 y
>       return s2
>  -}

Say run s0 x returns many different possibilities s1 (with varying
costs).  And suppose run s1 y is a (Left err) for some of these s1 and
a (Right whatever) for others.  When should the overall result of
run_and be a Left and when should it be a Right?  And *which error*
should you return if there's more than one Left?  Do you really want
to check whether every run s1 y is a (Right whatever)?  In that case
you are not gaining much from the laziness of ResultSet and might as
well use ResultSet'.  Until you decide the answer to questions of this
kind, you can't know how to best structure your code.

Regards,
Reid Barton