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
