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; 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
