[Haskell-beginners] How to write replicateM with interspersed guards?

[Brent Yorgey]

On Tue, Oct 04, 2011 at 05:27:59AM -0700, Sebastien Zany wrote:
> What would be the idiomatic way to write a function which expands to the
> following?
> 
> f n m = do {
> x1 <- m;
> guard (f [x1]);
> x2 <- m;
> guard (f [x1, x2]);
> .
> .
> .
> xn <- m;
> guard (f [x1,x2,...,xn]);
> }
> 
> What I'm trying to do is generate a list of lists of length n with some
> property (checked by f) efficiently.

Hmm, this is tricky.  I can't think of any nice idiomatic way to do it
-- if I really wanted something like this I'd just write an explicitly
recursive function to do it step by step.  One might hope to be able
to do it using something in the monad-loops package [1], but the
dependence of the tests on the list of results so far is a bit odd and
doesn't fit any of the patterns in that package.

The dependence of the tests on the whole list of results so far is
actually quite odd.  It looks like you are going to be repeating a lot
of work calling f successively on [x1], [x1,x2], [x1,x2,x3], ...  not
to mention that to construct these successive lists you are going to
have to append each new result to the end, which is O(n), making the
whole thing O(n^2).

I don't know anything about your function f, but I wonder whether you
might be able to express it in the form

  f = h . mappend . map g

for suitable functions h and g.  For example, if 

  f = (>10) . sum, 

then we could use 

  h = (>10) . getSum
  g = Sum

If so, rather than keeping the list of results so far as you iterate,
you can just keep the result of (mappend . map g).  Then when you
compute the next result you just apply g to it, combine it with the
previous result using `mappend`, then apply h to get a Bool for the
call to guard.

Alternatively, if f is insensitive to the order of its input list, you
could keep the list in reverse order so that successive results can be
*pre*pended in O(1); but this still (seemingly) wastes a lot of work.

-Brent

[1] http://hackage.haskell.org/package/monad-loops



> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners