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@haskell.org http://www.haskell.org/mailman/listinfo/beginners