"Lazy evaluation" ←→ composition with algebraic simplification.
On Fri, May 9, 2014 at 10:01 AM, Devon McCormick <[email protected]> wrote: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
