checko and subchecko work together to determine whether an ordered set of weights can produce integers 1 to 40 in reverse. It's more verbose since we are preserving the ability to run our program backwards - which is simply a byproduct of writing a purely relational program.
I'm curious if it can be written more concisely. Not sure. I note that most good solutions in Python and Haskell while fast and neat can only work in one direction. I would love to see purely relational versions in Haskell, Python etc. even if they involve bringing in a constraint solver (which alone isn't enough as far as I know) On Saturday, November 12, 2011, Ambrose Bonnaire-Sergeant < abonnaireserge...@gmail.com> wrote: > I'll just clarify, the "matches" function body jumps out at me. "checko" doesn't, but it's role in the problem is still clear, even if its implementation is not. I think that's still an important trait. > Can checko be improved? I'm not sure. What does subchecko do, David? > Ambrose > > On Sun, Nov 13, 2011 at 11:37 AM, Ambrose Bonnaire-Sergeant < abonnaireserge...@gmail.com> wrote: > > "Understandability" is subjective. The meaning of the cKanren really jumps out at me, the python program takes a lot more for me to think through. > There is nothing wrong with pruning the search space in this program. As you said, doing so reduced the Python program execution time to 2ms! > Ambrose > > On Sat, Nov 12, 2011 at 11:30 PM, Jules <julesjac...@gmail.com> wrote: > > The time difference is largely due to using the product library > function instead of for comprehensions and the fact that the cKanren > version cheats by hardcoding part of the solution, and hardcoding an > extra constraint alldiff(a,b,c,d). The following code takes ~12ms with > PyPy on my computer: > > def valid(a,b,c,d): > weights = set(w*a+x*b+y*c+z*d for w in [-1,0,1] > for x in [-1,0,1] > for y in [-1,0,1] > for z in [-1,0,1]) > return weights >= set(range(1,41)) > > > ws = [(a,b,c,d) for a in range(1,40) > for b in range(1,40) if a <= b > for c in range(1,40) if b <= c > for d in range(1,40) if c <= d > if a+b+c+d == 40 and valid(a,b,c,d)] > > If you cheat with `for a in [1]` instead of `for a in range(1,40)` and > changing the <= to < (the same cheat as the alldiff), then the > execution time drops to 2ms. > > Since we don't seem to be going to agree on the definition of > declarative, lets use another word: nice. Lets define niceness as > understandability and closeness to mathematical specification. I agree > that the matches definition is already nice: it handles the > constraints and symmetry breaking nicely (better than the Python > version if you ignore syntactic issues e.g. a+b+c+d=40 is more > convoluted). But the checko and subchecko leave a lot to be desired. > So my question is: can the cKanren version be improved so that it also > becomes nice? > > Jules > > On 12 nov, 07:16, David Nolen <dnolen.li...@gmail.com> wrote: >> Also note that even given all this generality over the Python code - the >> earlier Python implementation takes ~300ms and this implementation takes >> >> >900ms on my machine. >> >> Quite a bit slower than ~12ms. Inferring 40 takes even less time of course >> - ~8ms. >> >> But really the execution time is just icing on the declarative cake ;) >> >> David >> >> >> >> >> >> >> >> On Fri, Nov 11, 2011 at 8:09 PM, Jules <julesjac...@gmail.com> wrote: >> > Here is a new program. Perhaps you would consider this declarative: >> >> > def valid(a,b,c,d): >> > weights = set(w*a+x*b+y*c+z*d for (w,x,y,z) in >> > product([-1,0,1],repeat=4)) >> > return weights >= set(range(1,41)) >> >> > ws = [(a,b,c,d) for (a,b,c,d) in product(range(1,41),repeat=4) >> > if a <= b <= c <= d and a+b+c+d == 40 and >> > valid(a,b,c,d)] >> >> > On 12 nov, 01:48, Jules <julesjac...@gmail.com> wrote: >> > > Are we reading the same cKanren code? I'll give you that the matches >> > > definition is declarative, but then read checko and subchecko. They >> > > are all about (recursive) control flow. Where does the specification >> > > say anything remotely close to the checko and subchecko relations? In >> > > contrast to this, the Python set comprehensions have minimal control >> > > flow. Yeah, the standard Python implementation has a certain order of >> > > executing the comprehensions, but so does the cKanren implementation >> > > when executing the predicates. My Python program doesn't depend on > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
