Joachim Breitner | 15 Jan 10:57 2014
Picon

mdo with multiple values

Dear List,

a little puzzle. 

Given a monad M with a MonadFix instance, and these two functions:
        act1 :: T -> M ()
        act2 :: a -> M T

I morally want to write this function:
        foo :: [a] -> M ()
        foo = mdo
          mapM_ act1 xs
          xs <- mapM act2
          return ()

Unfortunately, that will not work: mapM_ will force xs before any of it
can be generated. But morally it should be possible, as the lists passed
to mapM_ and mapM have the same, already known list.

So here is my solution (which is a bit more general, because I happen to
need some that in one place):

        mapFstMapSnd :: MonadFix m => [(a -> m (), m a)] -> m ()
        mapFstMapSnd xs = const () `liftM` go xs (return [])
          where
            go [] cont = cont
            go ((f,s):xs) cont = mdo
                f v
                (v:vs) <- go xs $ do
                    vs <- cont
(Continue reading)

John Lato | 15 Jan 22:10 2014
Picon

Re: mdo with multiple values

Hello Joachim,

I don't really understand what you're doing here. There's the obvious

  mapM_ (act2 >=> act1)

But presumably act1 performs some monadic action that doesn't depend on its input, and you need that to be performed before act2?

To me, it feels like there's some sort of implicit coupling between act1 and act2, and you would be better off extracting that, perhaps by changing act1 to have the type act1 :: M T -> () .

If that's not possible, your approach seems pretty simple to me.

John L.

On Jan 15, 2014 1:57 AM, "Joachim Breitner" <mail <at> joachim-breitner.de> wrote:
Dear List,

a little puzzle.

Given a monad M with a MonadFix instance, and these two functions:
        act1 :: T -> M ()
        act2 :: a -> M T

I morally want to write this function:
        foo :: [a] -> M ()
        foo = mdo
          mapM_ act1 xs
          xs <- mapM act2
          return ()

Unfortunately, that will not work: mapM_ will force xs before any of it
can be generated. But morally it should be possible, as the lists passed
to mapM_ and mapM have the same, already known list.


So here is my solution (which is a bit more general, because I happen to
need some that in one place):

        mapFstMapSnd :: MonadFix m => [(a -> m (), m a)] -> m ()
        mapFstMapSnd xs = const () `liftM` go xs (return [])
          where
            go [] cont = cont
            go ((f,s):xs) cont = mdo
                f v
                (v:vs) <- go xs $ do
                    vs <- cont
                    v <- s
                    return (v:vs)
                return vs

Using that, I can write
        foo = mapFstSnd . map (x -> (act1, act2 x))


Are there better solutions? Simpler ones? Or possibly ones that do not
require a partial pattern?


Hmm, and thinking while writing lets me come up with

        data FunSplit m where
            FunSplit :: forall m a . (a -> m ()) -> m a -> FunSplit m

        mapFstMapSnd :: forall m. MonadFix m => [FunSplit m] -> m ()
        mapFstMapSnd xs = const () `liftM` go xs (return ())
          where
            go :: [FunSplit m] -> m b -> m b
            go [] cont = cont
            go (FunSplit f s:xs) cont = mdo
                f v
                (v,vs) <- go xs $ do
                    vs <- cont
                    v <- s
                    return (v,vs)
                return vs

        foo :: [SPut] -> SPut
        foo = mapFstMapSnd . map go
            where go x = FunSplit act1 (act2 x)

Any suggestions for improvement?


Thanks,
Joachim


--
Joachim Breitner
  e-Mail: mail <at> joachim-breitner.de
  Homepage: http://www.joachim-breitner.de
  Jabber-ID: nomeata <at> joachim-breitner.de


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Joachim Breitner | 16 Jan 00:24 2014
Picon

Re: mdo with multiple values

Dear John,

the background is a binary format assembler, so you can think of the
monad as the Put monad, only sufficiently lazy to admit a useful
MonadFix instance. Then one can do nice things like

        mdo 
          putWord32 offset
          putBS someMoreHeaderData
          ...
          offset <- getCurrentOffset
          putBS byteString1

where I conceptually use the offset before it is known.

So what if I want to put two offsets, followed by two bytestrings? Easy:

        mdo 
        putWord32 offset1
        putWord32 offset2
        putBS someMoreHeaderData
        ...
        offset1 <- getCurrentOffset
        putBS byteString1
        offset2 <- getCurrentOffset
        putBS byteString2

Now I try to generalize that to a list of Bytestrings, and just from the
looks of it, this is what you want to do:

     mdo 
        mapM_ putWord32 offsets
        putBS someMoreHeaderData
        ...
        offsets <- forM byteStrings $ \b -> 
           offset <- getCurrentOffset
           putBS b
           return offset

but that will <<loop>>.

Am Mittwoch, den 15.01.2014, 13:10 -0800 schrieb John Lato:
> Hello Joachim, 
> I don't really understand what you're doing here. There's the obvious
> 
>   mapM_ (act2 >=> act1)
> 
> But presumably act1 performs some monadic action that doesn't depend
> on its input, and you need that to be performed before act2?

Exactly, (act2 >=> act1) would write out the data in the wrong order.

> To me, it feels like there's some sort of implicit coupling between
> act1 and act2, and you would be better off extracting that, perhaps by
> changing act1 to have the type act1 :: M T -> () .
> 
> If that's not possible, your approach seems pretty simple to me. 

I don’t think its, possible with that signature, no...

(It were if I were to interleave the calls to act1 and act2, instead of
requiring first all act1 and then all act2, but then it would be trivial
anyways.)

Greetings,
Joachi

--

-- 
Joachim Breitner
  e-Mail: mail <at> joachim-breitner.de
  Homepage: http://www.joachim-breitner.de
  Jabber-ID: nomeata <at> joachim-breitner.de

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Heinrich Apfelmus | 16 Jan 11:34 2014
Picon

Re: mdo with multiple values

Joachim Breitner wrote:
> the background is a binary format assembler, so you can think of the
> monad as the Put monad, only sufficiently lazy to admit a useful
> MonadFix instance. Then one can do nice things like
> 
>         mdo 
>           putWord32 offset
>           putBS someMoreHeaderData
>           ...
>           offset <- getCurrentOffset
>           putBS byteString1
> 
> where I conceptually use the offset before it is known.
>         
> [..]     
> Now I try to generalize that to a list of Bytestrings, and just from the
> looks of it, this is what you want to do:
> 
>      mdo 
>         mapM_ putWord32 offsets
>         putBS someMoreHeaderData
>         ...
>         offsets <- forM byteStrings $ \b -> 
>            offset <- getCurrentOffset
>            putBS b
>            return offset
> 
> but that will <<loop>>.

So, the overall idea is that we can reserve 32 bits for the offset and 
defer its calculation to later. In other words,  putWord32  can "forward 
the file pointer" long before it actually writes the word.

Now, what's the problem with the `offsets` list? I think it may actually 
work in some monads that have a good MonadFix instance, but often, the 
MonadFix instances tend to be poor. One noteable example of the latter 
is the IO monad, and I have found the following rule to be very useful:

   To use value recursion in the IO monad, make sure
   that the sequence of *computations* is always
   defined in advance, only the values that these
   computations operate on may be lazy.

This rule is best explained with the problem at hand, by asking the 
following question: how many `putWord32` instructions does the following 
expression generate?

   mapM_ putWord32 offsets

Clearly, it should be `length offsets` many, but the problem is that 
this number is not known until the spine of `offsets` has been 
calculated. Now, some monads may be able to do that, but the rule for IO 
is that the number of `putWord32` must be known before the later 
definition of `offsets` can yield a value different from _|_ at all.

Now, if a recursive expression works in the IO monad, then it will work 
in any other monad as well.

Fortunately, we do known the spine of `offsets` in advance: it has the 
same spine as `byteStrings`. The solution is to make that explicit in 
the code, by using a lazy `zip`:

      ...
      mapM_ putWord32 (offsets `spine` byteStrings)
      ...

    where
    spine :: [a] -> [void] -> [a]
    spine ~[]     []     = []
    spine ~(x:xs) (y:ys) = x : tag xs ys

This code takes the spine of `byteStrings` and fills it with values from 
`offsets`.

It may also be possible to get rid of the <<loop>> by defining the monad 
appropriately: one pass calculates all offsets, a second pass calculates 
the actual output. The spine of `offsets` does not depend on the offset 
calculation, so there is a good chance that this might work recursively.

Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com
Joachim Breitner | 16 Jan 11:49 2014
Picon

Re: mdo with multiple values

Hi,

Am Donnerstag, den 16.01.2014, 11:34 +0100 schrieb Heinrich Apfelmus:
> Fortunately, we do known the spine of `offsets` in advance: it has the 
> same spine as `byteStrings`. The solution is to make that explicit in 
> the code, by using a lazy `zip`:
> 
>       ...
>       mapM_ putWord32 (offsets `spine` byteStrings)
>       ...
> 
>     where
>     spine :: [a] -> [void] -> [a]
>     spine ~[]     []     = []
>     spine ~(x:xs) (y:ys) = x : tag xs ys
> 
> This code takes the spine of `byteStrings` and fills it with values from 
> `offsets`.

I thought about something in that direction; but thanks for working it
out.

What I do not like about this solution is that it is not safe: As a
programmer I have two make sure that offsets and byteStrings actually
have the same length.

Greetings,
Joachim

--

-- 
Joachim Breitner
  e-Mail: mail <at> joachim-breitner.de
  Homepage: http://www.joachim-breitner.de
  Jabber-ID: nomeata <at> joachim-breitner.de

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane