[Haskell-beginners] Adding Either around a List monad?

[Mario Lang]

Benjamin Edwards <edwards.benj at gmail.com> writes:

> If you want to use monad transformers and have Either e [a] as the result
> type then you need Either to be the inner monad and List to be the outer
> monad. If you look at the types of EitherT (from the either package) and
> ListT from transformers this should hopefully make sense. Then you would
> keep the same impl as you have now, only you would need to "run" the ListT
> computation to yield Either e [a]. Anything that you would like to do
> inside of the inner Error monad will need to lifted inside of it using
> lift. Does that help you at all?
Hmm, sort of, and also not :-)  I finally managed to rewrite vs,
however, I used either to handle Either:

vs :: Music.Dur -> AmbiguousVoice -> Either e [Voice]
vs _ []     = return [[]]
vs l (x:xs) = either Left f $ pms l x where
  f pms = fmap concat $ sequence $
          pms >>= \pm ->
          return $ either Left (\pmss -> Right $ (pm :) <$> pmss) (vs (l - dur pm) xs)

It doesn't particularily look pretty, but I am rather relieved I finally
managed to make that change.  Took me roughly 4 attempts, a lot of
asking, and a few hours of playing around.  On the positive side, I have
learnt a lot.  However, I wonder if there is a more idiomatic way of
doing what I do above.  Took me a long time to realize there is a concat
missing.  I guess this is the result of sequence being used to collapse
the Eithers.

Thanks for helping by providing input.

> Ben
>
> On Mon, 5 Oct 2015 at 11:06 Mario Lang <mlang at delysid.org> wrote:
>
>> Hi.
>>
>> Consider this structure:
>>
>> vs :: Rational -> [Input] -> [[Output]]
>> vs _ []     = return []
>> vs l (x:xs) = pms l x >>= \pm -> (pm :) <$> vs (l - dur pm) xs
>>
>> pms :: Rational -> Input -> [Output]
>> pms l x = [x, x+1, x+2, ...] -- Just an example, not real code.
>>                              -- in reality, l is used to determine
>>                              -- the result of pms.
>>
>> This is basically traverse, but with a state (l) added to it.
>> So without the state, vs could be written as
>>
>> vs = traverse pms
>>
>> Now, I want to add Either e to this, like:
>>
>> vs :: Rational -> [Input] -> Either e [[Output]]
>> pms :: Rational -> Input -> Either e [Output]
>>
>> However, I have no idea how to implement vs.
>>
>> Interestingly, adding Either e to vs without changing the code lets it
>> compile, but it gives me the wrong result:
>>
>> vs :: Rational -> [Input] -> Either e [[Output]]
>> vs _ []     = return []
>> vs l (x:xs) = pms l x >>= \pm -> (pm :) <$> vs (l - pm) xs
>>
>> Since I am in the Either monad now, >>= does not do non-determinism, it
>> simply unwraps the Either from pms.  I have to admit, I dont fully
>> understand why this compiles, and what exactly it does wrong.  I only
>> see from testing that the results can't be right.
>>
>> On IRC, Gurkenglas suggested to use the State monad, like this:
>>
>> vs :: Rational -> [Input] -> Either e [[Output]]
>> vs l = `evalStateT l` . mapM v where
>>   v x = do l <- get
>>            pm <- lift $ pms l x
>>            put (l - dur pm)
>>            return pm
>>
>> This compiles, but also yields unexpected results.
>>
>> I have invested several hours now trying to add Either around this
>> algorithm, so that I can emit hard failures.  I am sort of frustrated
>> and out of ideas.  Somehow, I can't figure out what these
>> transformations actually change in behaviour.  I am being told, by quite
>> experienced Haskell programmers, that this is supposed to be correct,
>> but my testing tells me otherwise.  So before I just give up on this,
>> could someone please have a look and let me know if I have missed
>> something obvious?
>>
>> --
>> CYa,
>>   ⡍⠁⠗⠊⠕
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

-- 
CYa,
  ⡍⠁⠗⠊⠕ | Debian Developer <URL:http://debian.org/>
  .''`. | Get my public key via finger mlang/key at db.debian.org
 : :' : | 1024D/7FC1A0854909BCCDBE6C102DDFFC022A6B113E44
 `. `'
   `-      <URL:http://delysid.org/>  <URL:http://www.staff.tugraz.at/mlang/>