Thomas Costigliola-2 wrote: > > FYI, this a direct translation of a solution I did initially in ocaml. > I never actually ran the ocaml code because I didn't want to write the > string replacement and search functions or use the regexp library. The > interesting thing is that I had no desire to run it; [...] > Similar thing happened here: I first wrote down solution in LISP, a 6 lines recursive function that is btw somewhat similar to yours (haven't typed it yet though), and translation to J seemed like it would have been hairy, although after looking at your translation of ocaml code it does not seem anymore so hard.
[...] I was pretty > confident it was correct so I went directly to translating to J (most > of the time spent trying to shorten it as much as I could). > > Recursive > solutions, when written clearly, are easy to reason about and often > seem obviously correct. > > let rec rmarkov rules s k = match rules with > [] -> s > | (p,r,t)::rs -> if pattern_in s p then > (if t then substitute s p r else markov ((rev k)@(p,r,t)::rs) > (substitute s p r) []) > else markov rs s (p,r,t)::k;; > > I had a professor who once told me: "Recursion defines your worth as a > human being". > > > On Thu, Dec 17, 2009 at 10:42 AM, Thomas Costigliola <[email protected]> > wrote: >> Beware of the line wrap on the definition of 'markov'. >> >> On Thu, Dec 17, 2009 at 10:39 AM, Thomas Costigliola <[email protected]> >> wrote: >>> Here is a recursive tacit solution, again sans parsing. >>> >>> x=. @[ >>> y=. @] >>> pat=. 0&{::x >>> sub=. 1&{::x >>> term=.2&{::x >>> string=. 0&{::y >>> trash=. 1&{::y >>> EMPTY=. 0 3$a: >>> empty=. EMPTY"_ >>> patin=. {.x (pat (1:e.E.) ]) string >>> firstmatch=. [:{.[:I. pat E.] >>> rplcfirst=. (]}.~firstmatc...@pat) ,~ sub ,~ firstmatch {. ] >>> patsub=. {.x ((pat;sub) rplcfirst ]) string >>> patterm=. {.x term ] >>> markov=. string`(((}.x)$:(string ; [:<trash,{.x)) ` >>> ((((trash,[)$:(patsub;empty)) ` patsub ) @. patterm ) @. patin ) @. >>> (*...@#x) >>> NB. RULES markov STRING;EMPTY >>> >>> So others don't have to do the typing as well: >>> >>> NB. RULE=. PAT;SUB;TERMINAL >>> RULES1=. do;._2 ] 0 : 0 >>> 'A';'apple';0 >>> 'B';'bag';0 >>> 'S';'shop';0 >>> 'T';'the';0 >>> 'the shop';'my brother';0 >>> 'a never used';'terminating rule';1 >>> ) >>> >>> RULES2=. do;._2 ] 0 : 0 >>> 'A';'apple';0 >>> 'B';'bag';0 >>> 'S';'shop';1 >>> 'T';'the';0 >>> 'the shop';'my brother';0 >>> 'a never used';'terminating rule';1 >>> ) >>> >>> RULES3=. do;._2 ] 0 : 0 >>> 'A';'apple';0 >>> 'WWWW';'with';0 >>> 'Bgage';'->.*';0 >>> 'B';'bag';0 >>> '->.*';'money';0 >>> 'W';'WW';0 >>> 'S';'shop';1 >>> 'T';'the';0 >>> 'the shop';'my brother';0 >>> 'a never used';'terminating rule';1 >>> ) >>> >>> RULES4=. do;._2 ] 0 : 0 >>> '_+1' ; '_1+' ; 0 >>> '1+1' ; '11+' ; 0 >>> '1!' ; '!1' ; 0 >>> ',!' ; '!+' ; 0 >>> '_!' ; '_' ; 0 >>> '1*1' ; 'x,@y' ; 0 >>> '1x' ; 'xX' ; 0 >>> 'X,' ; '1,1' ; 0 >>> 'X1' ; '1X' ; 0 >>> '_x' ; '_X' ; 0 >>> ',x' ; ',X' ; 0 >>> 'y1' ; '1y' ; 0 >>> 'y_' ; '_' ; 0 >>> '1...@1' ; 'x,@y' ; 0 >>> '1...@_' ; '@_' ; 0 >>> ',@_' ; '!_' ; 0 >>> '++' ; '+' ; 0 >>> '_1' ; '1' ; 0 >>> '1+_' ; '1' ; 0 >>> '_+_' ; '' ; 0 >>> ) >>> >>> RULES1 markov 'I bought a B of As from T S.';EMPTY >>> I bought a bag of apples from my brother. >>> >>> RULES2 markov 'I bought a B of As from T S.';EMPTY >>> I bought a bag of apples from T shop. >>> >>> RULES3 markov 'I bought a B of As W my Bgage from T S.';EMPTY >>> I bought a bag of apples with my money from T shop. >>> >>> RULES4 markov '_1111*11111_';EMPTY >>> 11111111111111111111 >>> >>> >>> >>> On Wed, Dec 16, 2009 at 8:45 PM, Viktor Cerovski >>> <[email protected]> wrote: >>>> >>>> >>>> Andrew Nikitin wrote: >>>>> >>>>> >>>>>> For those who want to train their tacit muscles, here's a challenge. >>>>> >>>>>> A Markov algorithm is a specialized term rewriter. It accepts ... >>>>> >>>>> >>>>> >>>>> I am not sure the problem can be handled by tacit expressions better >>>>> than >>>>> with explicit expressions. >>>>> >>>>> Tacit way to implement 'while' is body^:predicate^:_ >>>>> >>>>> In J as it is there is no information flow between body and predicate, >>>>> but >>>>> for this problem there is a significant sharing of information. >>>>> predicate >>>>> is true when a non-terminal rule was applied and body is the >>>>> application >>>>> of this rule. >>>>> >>>>> >>>>> >>>>> Also, I belive, if you are demanding "tacit" solution, you should also >>>>> use >>>>> only tacitly defined utilities. stringreplace (which seems to be the >>>>> cornerstone of the algorithm) is not. >>>>> >>>>> >>>>> >>>>> Anyway, here is my submission (sans parsing) >>>>> >>>>> >>>>> >>>>> NB. This rules file is extracted from Wikipedia: >>>>> NB. http://en.wikipedia.org/wiki/Markov_Algorithm >>>>> R1=:i.0 3 >>>>> R1=:R1,'A';'apple';0 >>>>> R1=:R1,'B';'bag';0 >>>>> R1=:R1,'S';'shop';0 >>>>> R1=:R1,'T';'the';0 >>>>> R1=:R1,'the shop';'my brother';0 >>>>> R1=:R1,'a never used';'terminating rule';1 >>>>> >>>>> T1=:'I bought a B of As from T S.' >>>>> >>>>> >>>>> >>>>> mapply=: 4 : 0 >>>>> ri=.0 >>>>> while. ri<#x do. >>>>> z=.y E.~ p=.>{.r=.ri{x >>>>> ri=.1+ri >>>>> if. +./z do. >>>>> y=.((> 1 { r) , (#p) }. ])&.((z i. 1)&|.) y >>>>> ri=._*>{:r >>>>> end. >>>>> end. >>>>> y >>>>> ) >>>>> >>>>> [...] >>>>> >>>> >>>> Slightly shorter/faster/neater: >>>> >>>> mapply1=: 4 : 0 >>>> t=.ri=.0 >>>> while. (-.t) *. ri<#x do. >>>> 'p s t'=.ri{x >>>> y=.(s , (#p) }. ])&.((z i. 1)&|.)^:(f=.+./z=.p E. y) y >>>> ri=.(-.f)*ri+1 >>>> end. >>>> y >>>> ) >>>> >>>> -- >>>> View this message in context: >>>> http://old.nabble.com/Tacit-exercise-tp26818596s24193p26821788.html >>>> Sent from the J Programming mailing list archive at Nabble.com. >>>> >>>> ---------------------------------------------------------------------- >>>> For information about J forums see http://www.jsoftware.com/forums.htm >>>> >>> >> > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > > -- View this message in context: http://old.nabble.com/Tacit-exercise-tp26818596s24193p26835143.html Sent from the J Programming mailing list archive at Nabble.com. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
