[MPL] new run-time algorithm: for_all
Hello everyone, I recently created a MPL-based run-time algorithm named "for_all" which you can find at the following location: http://tinyurl.com/5a9d9d It is based on the "for_each" algorithm. The main difference is that it traverses a sequence of sequences and constructs new sequences that are then passed to a functor. Read the article for more information. I found it to be very useful in several cases, so I wanted to share it with the community. If you have any comments or spot any problems, please let me know. Regards, George ------------------------------------------------------------------------ George van Venrooij Organic Vectory http://www.organicvectory.com
George van Venrooij wrote:
I recently created a MPL-based run-time algorithm named "for_all" which you can find at the following location:
From a quick glance at the code, it seems to not be doing a simple traversal but a recursive traversal. Is that correct?
George van Venrooij wrote:
Hello everyone,
I recently created a MPL-based run-time algorithm named "for_all" which you can find at the following location:
It is based on the "for_each" algorithm. The main difference is that it traverses a sequence of sequences and constructs new sequences that are then passed to a functor. Read the article for more information.
I found it to be very useful in several cases, so I wanted to share it with the community. If you have any comments or spot any problems, please let me know.
It looks nice, but I have a few comments: 1) The name isn't informative. How about something like mpl::all_combinations to better say what the function actually does? 2) You should mention in the documentation that the number of sequences returned can get very big very fast. For instance, given six input sequences with 10 elements each, this function will return 1 million sequences of 6 elements each. Joe Gottman
On 11/22/08 07:59, Joe Gottman wrote: > George van Venrooij wrote: >> Hello everyone, >> >> I recently created a MPL-based run-time algorithm named "for_all" >> which you can find at the following location: >> >> http://tinyurl.com/5a9d9d >> >> It is based on the "for_each" algorithm. The main difference is that >> it traverses a sequence of sequences and constructs new sequences that >> are then passed to a functor. Read the article for more information. [snip] > 1) The name isn't informative. How about something like > mpl::all_combinations to better say what the function actually does? > > 2) You should mention in the documentation that the number of > sequences returned can get very big very fast. For instance, given six > input sequences with 10 elements each, this function will return 1 > million sequences of 6 elements each. From Joe's comment, it sounds like for_all is the same as the answer to exercise 7-8 of: http://www.boostpro.com/mplbook/ So, a better name, IMHO, would be something with cross_product in the name, or maybe cartesian_product or outer_product. IIRC, outer_product is what apl calls that operation. Anyway, I've posted an answer to exercise 7-8 at: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?CPPTM_Answers_-_Exercise_7-8 Currently, I'm learning haskell, and they have a way, using a list monad, to do the same, AFAICT. See: http://www.muitovar.com/monad/moncow.xhtml#list There, the function is called cross. IIRC, FC++ or someone connected with FC++: http://sourceforge.net/projects/fcpp/ has a monad template. It would be interesting to try and use a c++ list monad to solve the problem. I'll probably try it eventually, but maybe someone else would like to try. Who knows, a monad solution may have some advantage.
On 11/22/08 18:34, Larry Evans wrote:
On 11/22/08 07:59, Joe Gottman wrote:
George van Venrooij wrote:
Hello everyone,
I recently created a MPL-based run-time algorithm named "for_all" which you can find at the following location:
http://tinyurl.com/5a9d9d [snip]
Judging from the "what is it?" on that tinyurl, it is the cross product of the mplbook's exercise 7-8 mentioned in my previous post.
Currently, I'm learning haskell, and they have a way, using a list monad, to do the same, AFAICT. See:
http://www.muitovar.com/monad/moncow.xhtml#list
There, the function is called cross.
[snip] To get some idea of how haskell did it, I laboriously went through a manual trace of the haskell code. It's in the cross.log file of the cross.zip just uploaded to the boost vault under the Template Metaprogramming directory.
Larry Evans wrote:
Judging from the "what is it?" on that tinyurl, it is the cross product of the mplbook's exercise 7-8 mentioned in my previous post.
It indeed has similar behavior when feeding it 2 sequences as the cross product, or to be more precise, an outer product (as you mentioned earlier) since both sequences need not have the same length. Looking at Wikipedia's definition: http://en.wikipedia.org/wiki/Outer_product then my algorithm produces the outer product when called with 2 sequences. When called with 3 sequences, it generates some kind of 3-way outer product that I am not able to find a good name or definition for. Regards, George ------------------------------------------------------------------------ George van Venrooij Organic Vectory http://www.organicvectory.com
On 11/23/08 11:43, George van Venrooij wrote:
Larry Evans wrote:
Judging from the "what is it?" on that tinyurl, it is the cross product of the mplbook's exercise 7-8 mentioned in my previous post.
It indeed has similar behavior when feeding it 2 sequences as the cross product, or to be more precise, an outer product (as you mentioned earlier) since both sequences need not have the same length.
Looking at Wikipedia's definition: http://en.wikipedia.org/wiki/Outer_product then my algorithm produces the outer product when called with 2 sequences. When called with 3 sequences, it generates some kind of 3-way outer product that I am not able to find a good name or definition for. In the cross.zip file mentioned in my previous post and located here:
http://www.boostpro.com/vault/index.php?PHPSESSID=ab51206c9d980155d142f5bcef... you can see cross.out, which contains the output from a sort of 3 way outer product which seems like just an outer product of of a sequence and a previous outer product. IOW, a fold of cross over a sequence of sequences should result in an n-way outer product. I haven't tried it yet; however, it should be very simple to do in cross.hs since haskell already has a fold function.
On 11/23/08 12:39, Larry Evans wrote: [snip]
In the cross.zip file mentioned in my previous post and located here:
http://www.boostpro.com/vault/index.php?PHPSESSID=ab51206c9d980155d142f5bcef...
[snip] I requested help in the haskell.cafe ng and that resulted in a much better haskell solution: http://thread.gmane.org/gmane.comp.lang.haskell.cafe/47985 Maybe someone will get around to translating that to mpl. It would be interesting to compare the compile times.
Joe Gottman wrote:
1) The name isn't informative. How about something like mpl::all_combinations to better say what the function actually does?
I admit the name is terrible :-) It's a placeholder until I can find out how it should be called. I've considered using the word "combinations", but in statistics it has a different meaning than what this algorithm does, so that's why I didn't pick it.
2) You should mention in the documentation that the number of sequences returned can get very big very fast. For instance, given six input sequences with 10 elements each, this function will return 1 million sequences of 6 elements each.
Good suggestion, I should add this as a caution to the user. ------------------------------------------------------------------------ George van Venrooij Organic Vectory http://www.organicvectory.com
I admit the name is terrible :-) It's a placeholder until I can find out how it should be called.
I think it's technically an n-ary Cartesian Product: http://en.wikipedia.org/wiki/Cartesian_product, though I think other languages just call it a Cartesian Product: http://www.sagemath.org/doc/ref/module-sage.combinat.cartesian-product.html. James
James Philbin wrote:
I think it's technically an n-ary Cartesian Product: http://en.wikipedia.org/wiki/Cartesian_product, though I think other languages just call it a Cartesian Product: http://www.sagemath.org/doc/ref/module-sage.combinat.cartesian-product.html.
James
Thanks James, this is exactly what I was looking for. I will rename it to cartesian_product. By the way, is it possible to submit new algorithms for possible inclusion into the MPL? Or is the library considered to be "finished"? ------------------------------------------------------------------------ George van Venrooij Organic Vectory http://www.organicvectory.com
On 11/24/08 09:46, George van Venrooij wrote:
James Philbin wrote:
I think it's technically an n-ary Cartesian Product: http://en.wikipedia.org/wiki/Cartesian_product, though I think other languages just call it a Cartesian Product: http://www.sagemath.org/doc/ref/module-sage.combinat.cartesian-product.html.
James
Thanks James, this is exactly what I was looking for. I will rename it to cartesian_product.
By the way, is it possible to submit new algorithms for possible inclusion into the MPL? Or is the library considered to be "finished"?
George, earlier this year, there was yet another person who had a proposed solution: http://thread.gmane.org/gmane.comp.lib.boost.devel/171761 The OP in that thread benchmarked the solution: http://thread.gmane.org/gmane.comp.lib.boost.devel/171761/focus=172030 I'd guess that before anything is adopted when there are several alternatives, the pros/cons and a benchmark comparing the alternatives would be desirable. -regards, Larry
On 11/24/08 10:54, Larry Evans wrote:
On 11/24/08 09:46, George van Venrooij wrote: [snip] George, earlier this year, there was yet another person who had a proposed solution:
http://thread.gmane.org/gmane.comp.lib.boost.devel/171761
The OP in that thread benchmarked the solution:
http://thread.gmane.org/gmane.comp.lib.boost.devel/171761/focus=172030
I'd guess that before anything is adopted when there are several alternatives, the pros/cons and a benchmark comparing the alternatives would be desirable.
apfelmus' recent post to haskell.cafe ng provided a monadic version: sequence :: Monad m => [m a] -> m [a] {-# INLINE sequence #-} sequence ms = foldr k (return []) ms where k m m' = do { x <- m; xs <- m'; return (x:xs) } of the crossf solution posted earlier: http://news.gmane.org/gmane.comp.lang.haskell.cafe/cutoff=47985 which looks very similar to the moncow 2 sequence version: cross :: [a] -> [b] -> [(a,b)] cross ls1 ls2 = do x <- ls1 y <- ls2 return (x,y) found here: http://www.muitovar.com/monad/moncow.xhtml#list which was mentioned in my first reply. This suggests, at least to me, that monads could be useful in mpl. Anybody else think that's worth exploring?
Hi, I have renamed the algorithm to "cartesian_product" and modified the article to include some of the feedback. http://tinyurl.com/55wdww Since it serves my needs for now, I have no plans to develop it further. ------------------------------------------------------------------------ George van Venrooij Organic Vectory http://www.organicvectory.com
participants (5)
-
George van Venrooij -
James Philbin -
Joe Gottman -
Larry Evans -
Mathias Gaunard