I don't think scanl can work here, since the monadic action has to be applied to the result of previous one and will have a side effect, so if you build a list like [return i, return i >>= f, return i >>= f >>= f, ...] the first action will do nothing, the second action will have a single side effect, but the third one will have 3 side effects instead of 2, because it operates on the side-effect performed by the second one. This seems to work (a combination of manual state monad and foldM, I could also have used a state monad transformer I guess) iterateM n f i = foldM collectEffect (i,[]) (replicate n f) >>= return . reverse . snd where collectEffect (x,rs) f = f x >>= \y -> return (y,y:rs) Ugly test: var = unsafePerformIO $ newIORef 0 inc i = do x <- readIORef var let y = x+i writeIORef var y return y results in *Main> iterateM 10 inc 1 [1,2,4,8,16,32,64,128,256,512] *Main> iterateM 10 inc 1 [513,1026,2052,4104,8208,16416,32832,65664,131328,262656] but maybe this is not what you're looking for? On Wed, Apr 8, 2009 at 5:30 PM, Thomas Davie wrote:

On 8 Apr 2009, at 17:20, Jonathan Cast wrote:

On Wed, 2009-04-08 at 16:57 +0200, Thomas Davie wrote:

...

...

We have two possible definitions of an "iterateM" function:

iterateM 0 _ _ = return [] iterateM n f i = (i:) <$> (iterateM (n-1) f =<< f i)

iterateM n f i = sequence . scanl (>>=) (return i) $ replicate n f

The former uses primitive recursion, and I get the feeling it should be better written without it. The latter is quadratic time – it builds up a list of monadic actions, and then runs them each in turn.

It's also quadratic in invocations of f, no? If your monad's (>>=) doesn't object to being left-associated (which is *not* the case for free monads), then I think

iterateM n f i = foldl (>>=) (return i) $ replicate n f

But this isn't the same function – it only gives back the final result, not the intermediaries.

Bob_______________________________________________

Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Well okay, I don't really need the state since it is already in the list... So cleaned up iterateM n i = fmap (tail . reverse) . foldM collectEffect [i] . replicate n where collectEffect xxs@(x:xs) f = fmap (:xxs) (f x) But I'm sure it can be much simpler (I don't understand Claus' version :-) On Wed, Apr 8, 2009 at 6:38 PM, Peter Verswyvelen wrote:

Oh, I could have written it in more point free style (with arguments reversed) as iterateM n i = fmap (reverse . snd) . foldM collectEffect (i,[]) . replicate n where collectEffect (x,rs) f = f x >>= \y -> return (y,y:rs)

and I'm sure collectEffect could also be improved, but I'm still in newbieeee land

On Wed, Apr 8, 2009 at 6:33 PM, Peter Verswyvelen wrote:

...

I don't think scanl can work here, since the monadic action has to be applied to the result of previous one and will have a side effect, so if you build a list like [return i, return i >>= f, return i >>= f >>= f, ...]

the first action will do nothing, the second action will have a single side effect, but the third one will have 3 side effects instead of 2, because it operates on the side-effect performed by the second one.

This seems to work (a combination of manual state monad and foldM, I could also have used a state monad transformer I guess)

iterateM n f i = foldM collectEffect (i,[]) (replicate n f) >>= return . reverse . snd where collectEffect (x,rs) f = f x >>= \y -> return (y,y:rs)

Ugly test:

var = unsafePerformIO $ newIORef 0

inc i = do x <- readIORef var let y = x+i writeIORef var y return y

results in

*Main> iterateM 10 inc 1 [1,2,4,8,16,32,64,128,256,512] *Main> iterateM 10 inc 1 [513,1026,2052,4104,8208,16416,32832,65664,131328,262656]

but maybe this is not what you're looking for?

On Wed, Apr 8, 2009 at 5:30 PM, Thomas Davie wrote:

...

On 8 Apr 2009, at 17:20, Jonathan Cast wrote:

On Wed, 2009-04-08 at 16:57 +0200, Thomas Davie wrote:

...

...

We have two possible definitions of an "iterateM" function:

iterateM 0 _ _ = return [] iterateM n f i = (i:) <$> (iterateM (n-1) f =<< f i)

iterateM n f i = sequence . scanl (>>=) (return i) $ replicate n f

The former uses primitive recursion, and I get the feeling it should be better written without it. The latter is quadratic time – it builds up a list of monadic actions, and then runs them each in turn.

It's also quadratic in invocations of f, no? If your monad's (>>=) doesn't object to being left-associated (which is *not* the case for free monads), then I think

iterateM n f i = foldl (>>=) (return i) $ replicate n f

But this isn't the same function – it only gives back the final result, not the intermediaries.

Bob_______________________________________________

Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

|No indeed – that's what I meant about the latter being quadratic – it |runs the action far more times than the other. 'quadratic time' usually refers to complexity, not different results, so I thought I'd mention it anyway. |ghci tells me this: |Prelude Control.Applicative Control.Arrow> let iterateM' = let f `op` |x = uncurry (<$>) . ((:) &&& ((x=<<) . f)) in (foldr op (const $ |return []) .) . replicate | |<interactive>:1:92: | Ambiguous type variable `m' in the constraints: | `Monad m' arising from a use of `return' at <interactive>: |1:92-100 | `Functor m' arising from a use of `op' at <interactive>:1:80-81 | Probable fix: add a type signature that fixes these type |variable(s) But surely you have not enabled the monomorphism restriction while avoiding explicit recursion?-) I should, of course, have removed those nasty points - sorry about that, hope noone got hurt - to leave us with: (foldr (flip (((uncurry (<$>).).).((((:)&&&).).((.).(=<<))))) (const $ return []).) . replicate there, much better, isn't it? So obvious and clear that it doesn't even need a name anymore - it is fully declarative and self-explanatory. And it typechecks, so it must be correct!-) And it passes a test, so it isn't wrong, either!-) *Main> ((foldr (flip (((uncurry (<$>).).).((((:)&&&).).((.).(=<<))))) (const $ return []).) . replicate) 3 print () () () () [(),(),()] Sorry, just couldn't resist:-) Now, how do I get that tongue out of my cheek?-) Claus

On 8 Apr 2009, at 19:05, Josef Svenningsson wrote:

On Wed, Apr 8, 2009 at 4:57 PM, Thomas Davie wrote:

...

We have two possible definitions of an "iterateM" function:

iterateM 0 _ _ = return [] iterateM n f i = (i:) <$> (iterateM (n-1) f =<< f i)

iterateM n f i = sequence . scanl (>>=) (return i) $ replicate n f

The former uses primitive recursion, and I get the feeling it

should be better written without it. The latter is quadratic time – it builds up a list of monadic actions, and then runs them each in turn.

...

Can anyone think of a version that combines the benefits of the two?

There seems to be a combinator missing in Control.Monad. Several people have suggested that iterateM should be implemented using a fold. But that seems very unnatural, we're trying to *build* a list, not *consume* it. This suggests that we should use an unfold function instead. Now, I haven't found one in the standard libraries that works for monads but arguably there should be one. So, let's pretend that the following function exists: unfoldM :: Monad m => (b -> m (Maybe(a,b))) -> b -> m [a]

Then the implementation of iterateM becomes more natural: \begin{code} iterateM n f i = unfoldM g (n,i) where g (0,i) = return Nothing g (n,i) = do j <- f i return (Just (i,(n-1,j))) \end{code} I'm not sure whether this version is to your satisfaction but it's quite intuitive IMHO.

That one certainly seems very natural to me, now if only unfoldM existed :) Bob