If there was ever a a candidate for "lazy evaluation", "catalog" would be it.
On Fri, May 9, 2014 at 1:00 PM, Devon McCormick <[email protected]> wrote: > I've used "catalog" in real-world apps but, as Dan indicates, it was with > arguments that gave fairly small results. > > > > On Thu, May 8, 2014 at 8:30 PM, 'Pascal Jasmin' via Programming < > [email protected]> wrote: > >> > one reason for its rarity is, at least, that in any real-world context, >> a complete MxN catalog would be prohibitively expensive >> >> its very cheap compared to A. and filtering permutations after you've >> generated them. In the resource matching application I linked to, where 1 >> user ends up with 1 resource, its also possible to prefilter the arguments >> to catalogue removing options where forced choices exist, and thus >> significantly reducing an exponential algorithm to allow solutions to >> moderately large problem spaces. >> >> Its fast compared to backtracking loop solutions in other languages even >> when they abort after finding first valid set of matches. It seems like a >> very clean J way of approaching fairly hard problems. Polynomial and >> higher problems benefit from strategies that reduce search space. >> >> Using catalogue to analyze n moves with an average x possibilities per >> move has an expensive x ^ n search space. But reducing any move >> possibility to 1 reduces both average x, and reduces n by 1 >> >> >> ----- Original Message ----- >> From: Dan Bron <[email protected]> >> To: "[email protected]" <[email protected]> >> Cc: >> Sent: Thursday, May 8, 2014 6:39:14 PM >> Subject: Re: [Jprogramming] a cool permutation verb >> >> I don't see catalog used frequently in natural J code. It does come up on >> these Forums from time to time, mostly in contrived situations. In my own >> code, I sometimes use it to generate J sentences in order to compare >> performance statistics for semantically-equivalent phrases. But outside of >> that, I don't see it too often. I suspect one reason for its rarity is, at >> least, that in any real-world context, a complete MxN catalog would be >> prohibitively expensive. >> >> So it's unsurprising that APL didn't have a primitive catalog function. >> Of course, you could express it as {jot} {dot} {comma}, dot as being outer >> product (and jot in this context a placeholder, not unlike [:) with the >> usual caveats about the differences between J's rank and APL's >> multidimensionality (ie you could expect catalog to work for 1D vectors in >> APL and generalized lists in J). >> >> So, when he got his chance to "rationalize" APL and rebuild it from >> the ground up as J, did Ken have a change of heart about catalog's >> centrality to the discipline of computer science? Is that why he assigned >> to it that scarce and desirable resource, a primitive spelling? A >> one-character primitive, no less? >> >> I suspect not. Recall the other valence of {, to wit: from. You might >> think having this kind of partner is an even greater endorsement of >> catalog's virtues ... until you realize: >> >> row_2n3n6_col_7n13 =: 2 3 6 ; 7 13 >> table =: i. 10 20 >> >> (< row_2n3n6_col_7n13) { table NB. "from" >> 47 53 >> 67 73 >> 127 133 >> >> ({ row_2n3n6_col_7n13) NB. "catalog" >> +---+----+ >> |2 7|2 13| >> +---+----+ >> |3 7|3 13| >> +---+----+ >> |6 7|6 13| >> +---+----+ >> >> ({ row_2n3n6_col_7n13) { table NB. "catalog from" >> 47 53 >> 67 73 >> 127 133 >> >> Ah, "from" *is* "catalog". Catalog is a primitive because from needed a >> thematically related definition for monad { (and from, of course, got a >> precious one-character primitive because it *is* central to array >> programming). And, incidentally, this is why the results of catalog are >> boxed, even though they don't need to be, and we end up writing >@:{ >> instead of plain { every time we use it. >> >> That is, by definition, the results of { will be homogenous in both type >> and shape, and so we know for certain boxes aren't required ... except that >> dyad { has a scalar left rank, and so to completely address an atom (or >> anything more granular than an item, ie a Cartesian point in the frame >> specified as a vector of indices, one per axis), each selection must be >> boxed. >> >> True story. >> >> -Dan >> >> >> >> Sent from my iPhone >> >> >> > On May 8, 2014, at 5:34 PM, "'Pascal Jasmin' via Programming" < >> [email protected]> wrote: >> > >> > Its the same. Just more descriptive name than catalogue perhaps. >> Google seems to only find J references to query "catalogue function >> permutations". I feel as though catalogue and my use of it is a >> generalizable pattern, and the J designers agreed, but I don't know if >> other languages did something similar, and just used a different name? >> > >> > Was catalogue in APL? >> > >> > >> > ----- Original Message ----- >> > From: David Lambert <[email protected]> >> > To: programming <[email protected]> >> > Cc: >> > Sent: Thursday, May 8, 2014 4:50:40 PM >> > Subject: Re: [Jprogramming] a cool permutation verb >> > >> > Indeed cool, does it differ from ,@{ :[: >> >> Date: Thu, 8 May 2014 10:53:53 -0700 (PDT) >> >> From: "'Pascal Jasmin' via Programming"<[email protected]> >> >> To: Programming forum<[email protected]> >> >> Subject: [Jprogramming] a cool permutation verb >> >> Message-ID: >> >> <[email protected]> >> >> Content-Type: text/plain; charset=utf-8 >> >> >> >> cperm =: [: , [: < "1 [: > [: ,"0 1/ each/ (_2&}. , [: ,"0 0/ each/ >> _2&{.) >> >> >> >> this creates constrained permutations where each position in the list >> can only be drawn from its own set: >> >> >> >> ? ?cperm 3 4 ; 1 2 >> >> ????????????????? >> >> ?3 1?3 2?4 1?4 2? >> >> ????????????????? >> >> >> >> ? ?cperm 0 ; 3 4 ; 1 2; 5 >> >> ????????????????????????????????? >> >> ?0 3 1 5?0 3 2 5?0 4 1 5?0 4 2 5? >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> > > > > -- > Devon McCormick, CFA > > -- Devon McCormick, CFA ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
