Inline comments follow... > I will have to think about that... > > First a few obvious notes: > > (1) I said "often" not "always". > (2) This is doubly recursive and ^: is more like tail recursion >
One can always produce a tacit verb which performs the quicksort computations (or the computations of any other verb) using only a single loop of the form (u^:v^:_), in theory. However, in practice... > That said, we can do array traversal at each level of induction, which > we might be able to use here. We might have to pay a little extra in > boxing overhead, but double recursion already carries its own costs - > it would at least be interesting to compare implementations, even if > it's not better. Indeed. > > That said, my initial efforts have a problem detecting when we are > done. (Also, in my first approach we get some extra processing that > would not happen when one side needs deeper recursion than the other.) > I appreciate your efforts. > But there's more than one way to approach this (we can have stacks and > state machines as parts of our data structure, for that matter), and I > might think of a good one after sleeping on it. (Or, I might not, I'm > just not sure yet.) > > Thanks, On Fri, Oct 6, 2017 at 6:00 PM, Raul Miller <[email protected]> wrote: > I will have to think about that... > > First a few obvious notes: > > (1) I said "often" not "always". > (2) This is doubly recursive and ^: is more like tail recursion > > That said, we can do array traversal at each level of induction, which > we might be able to use here. We might have to pay a little extra in > boxing overhead, but double recursion already carries its own costs - > it would at least be interesting to compare implementations, even if > it's not better. > > That said, my initial efforts have a problem detecting when we are > done. (Also, in my first approach we get some extra processing that > would not happen when one side needs deeper recursion than the other.) > > But there's more than one way to approach this (we can have stacks and > state machines as parts of our data structure, for that matter), and I > might think of a good one after sleeping on it. (Or, I might not, I'm > just not sure yet.) > > Thanks, > > -- > Raul > > > On Fri, Oct 6, 2017 at 5:36 PM, Jose Mario Quintana > <[email protected]> wrote: > > Can you show us the exact tacit induction or analytical fixed version of, > > > > quicksort=. (($:@(< # [) , (= # [) , $:@(> # [)) ({~ ?@#))^:(1 < #) > > > > ? > > > > No, I do not want to replace quicksort by /:~ . (Actually, I am, > > ultimately, interested in (quicksort=. (($:@(< # [) , (= # [) , $:@(> # > [)) > > ({~ v@#))^:(1 < #) ) where v is tacit and fixed verb having the same > > meaning as ? but with different innerworks for the random generation > > process.) > > > > > > > > On Thu, Oct 5, 2017 at 8:15 PM, Raul Miller <[email protected]> > wrote: > > > >> J does not have an explicit scope for $: (other than using an explicit > >> verb for that purpose), but often you can use induction instead of > >> recursion. > >> > >> (And, also - generally speaking - we can use analytic techniques - for > >> example, sometimes recursive algorithms can be replaced with > >> arithmetic.) > >> > >> Thanks, > >> > >> -- > >> Raul > >> > >> > >> > >> On Thu, Oct 5, 2017 at 7:57 PM, Jose Mario Quintana > >> <[email protected]> wrote: > >> > " > >> > If the first example was in an equivalent to tacit code, it could not > >> > call f. It would have to be like this: > >> > 4 (.x).`(.y (. y , x + {: y ). x $: <: y). at .(.x < y). 8 > >> > It would be impossible to use in a larger tacit program and you'd need > >> > Jx to solve that, as far as I understand. > >> > Same problem as in tacit J today. > >> > I didn't manage to use $: from explicit J. > >> > /Erling > >> > > >> > On 2017-09-30 18:28, Erling Hellenäs wrote: > >> >> Hi all ! > >> >> > >> >> 4(f=. 4 : 'x (4 : ''x'')`(4 : ''s,y +{: s=.x f <: y'')@.(4 :''x > < > >> >> y'') y' )8 > >> >> > >> >> 4 9 15 22 30 > >> > " > >> > > >> > Beware of line-wrapping... > >> > > >> > One can always produce, in principle, for any explicit verb a > >> corresponding > >> > tacit verb. Ocasionally, this might be a difficult task; this is not > in > >> > this case, > >> > > >> > 4 (f=. 4 : 'x (4 : ''x'')`(4 : ''s,y +{: s=.x f <: y'')@.(4 :''x < > >> y'') > >> > y' ) 8 > >> > 4 9 15 22 30 > >> > > >> > 4 (f=. [`(] (] , [ + {:@:]) [ $: <:@:])@.<) 8 > >> > 4 9 15 22 30 > >> > > >> > After I rewrote f tacitly I realized that this explicit verb was the > >> > transcription of a tacit verb :D (although I suspect the original > tacit > >> > verb itself was a transcription of an explicit version). > >> > > >> > " > >> > 4 (.x).`(.y (. y , x + {: y ). x $: <: y). at .(.x < y). 8 > >> > It would be impossible to use in a larger tacit program and you'd need > >> > " > >> > > >> > At any rate, it is very easy, in Jx, to embed a tacit version of the > >> verb f > >> > within a larger tacit verb and fix it, for instance, > >> > > >> > 4 (1 + f) 8 > >> > 5 10 16 23 31 > >> > > >> > 4 (1 + f)f. 8 > >> > 5 10 16 23 31 > >> > > >> > The reason is Jx's recursive scope O.0, > >> > > >> > (1 + f)f. > >> > 1 + [`(] (] , [ + {:@:]) [ $: <:@:])@.<O.0 > >> > > >> > One cannot do that in J, > >> > > >> > JVERSION > >> > Engine: j806/j64avx/windows > >> > Beta-6: commercial/2017-09-26T14:05:48 > >> > Library: 8.06.07 > >> > Qt IDE: 1.6.1/5.6.3 > >> > Platform: Win 64 > >> > Installer: J806 install > >> > InstallPath: c:/program files/j64-806 > >> > Contact: www.jsoftware.com > >> > > >> > 4 (f=. [`(] (] , [ + {:@:]) [ $: <:@:])@.<) 8 > >> > 4 9 15 22 30 > >> > > >> > 4 (1 + f) 8 > >> > 5 10 16 23 31 > >> > > >> > 4 (1 + f)f. 8 > >> > 5 10 16 23 31 > >> > > >> > (1 + f)f. NB. The larger verb in not a (pure) tacit verb > anymore... > >> > 1 + 3 : '[`(] (] , [ + {:@:]) [ $: <:@:])@.< y' :(4 : 'x [`(] (] , [ + > >> > {:@:]) [ $: <:@:])@.< y') > >> > > >> > unless, one is prepared to use the darkest side of the force (which Jx > >> > promotes), see [0, 1] > >> > > >> > 4 (1 + (f f.)dRS) 8 > >> > 5 10 16 23 31 > >> > > >> > (1 + (f f.)dRS) > >> > 1 + ,^:(0:``:)&6 :.(<@:((,'0') ,&:< ]))@:([ , (<[`(] (] , [ + {:@:]) > [ $: > >> > <:@:])@.<) , ])&:(<@:((,'0') ,&:< ])) > >> > > >> > This is just one of the otherwise apparently impossible feats for > those > >> who > >> > choose to always obey the Dictionary's sacred commandments ;) > >> > > >> > References > >> > > >> > [0] [Jprogramming] Adverbial Tacit Jym Jose Mario Quintana > >> > http://www.jsoftware.com/pipermail/programming/2016-May/ > 045156.html > >> > > >> > [1] J Wicked Toolkit > >> > http://www.2bestsystems.com/foundation/j/Jx.zip > >> > \Jx\J\J Wicked Toolkit.ijs > >> > > >> > > >> > On Sat, Sep 30, 2017 at 12:57 PM, Erling Hellenäs < > >> [email protected]> > >> > wrote: > >> > > >> >> If the first example was in an equivalent to tacit code, it could not > >> call > >> >> f. It would have to be like this: > >> >> 4 (.x).`(.y (. y , x + {: y ). x $: <: y).@.(.x < y). 8 > >> >> It would be impossible to use in a larger tacit program and you'd > need > >> Jx > >> >> to solve that, as far as I understand. > >> >> Same problem as in tacit J today. > >> >> I didn't manage to use $: from explicit J. > >> >> /Erling > >> >> > >> >> > >> >> On 2017-09-30 18:28, Erling Hellenäs wrote: > >> >> > >> >>> Hi all ! > >> >>> > >> >>> 4(f=. 4 : 'x (4 : ''x'')`(4 : ''s,y +{: s=.x f <: y'')@.(4 > :''x < > >> >>> y'') y' )8 > >> >>> > >> >>> 4 9 15 22 30 > >> >>> > >> >>> Here we have another example of the Henry syntax: > >> >>> > >> >>> 4(f=.(.x (.x).`(.y (. y , x + {: y ). x f <: y).@.(.x < y). y).)8 > >> >>> > >> >>> s is here the right unnamed operand of (. y , x + {: y ). . As > long as > >> >>> you have variables, like in explicit code, you can keep s if you > want. > >> Like > >> >>> this: > >> >>> > >> >>> 4(f=.(.x (.x).`(. s , y + {: s=. x f <: y).@.(.x < y). y).)8 > >> >>> > >> >>> > >> >>> Cheers, > >> >>> > >> >>> Erling > >> >>> > >> >>> > >> > >> > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
