Perl 6 - the future is here, just unevenly distributed

IRC log for #rosettacode, 2013-08-12

| Channels | #rosettacode index | Today | | Search | Google Search | Plain-Text | summary

All times shown according to UTC.

Time Nick Message
00:49 mikemol joined #rosettacode
03:10 RRR2 Is there a good way to match a subarray in a array?
03:11 sorear in what language?
03:11 RRR2 Java
03:12 RRR2 I guess anyway would work with most languages
03:12 RRR2 any way*
03:14 RRR2 it's almost like a String indexof but with Arrays
03:15 ttmrichter RRR2: What do you mean by "match a subarray in an array"?
03:16 RRR2 Something like match [4,5,6] in [1,2,3,4,5,6,7,8,9] the index of it..
03:18 ttmrichter In Prolog I could probably write decently readable code for that.
03:19 ttmrichter Harder to write readable code in other languages for it because you'd have to write the backtracking/memoization yourself.
03:19 RRR2 I don't know Prolog but I'll take it.
03:20 ttmrichter The algorithm would be the same as its string counterpart.
03:20 RRR2 Too bad the methods of the strings are on native code
03:30 ttmrichter Well, I've got some Prolog code that will find the first such substring.
03:30 ttmrichter Unfortunately it's not finding ALL such substrings.  Need some debugging time.
03:34 ttmrichter Hmm...  INteresting.
03:42 ttmrichter RRR2: http://ideone.com/cFgCRN
03:42 fedaykin "Ideone.com | cFgCRN"
03:42 sorear how big are your arrays?  how many subarrays do you want to match?
03:42 sorear do you need to use boyer-moore or rabin-karp or something to meet your performance goals?
03:42 ttmrichter That's the code that finds the first subarray in Prolog.  Simple and if you can read reasonably clear declarative Prolog you'll see the technique.
03:43 ttmrichter The more general code that can find all subarrays is not so trivial (yet).  I'm investigating farther.
03:43 sorear if you're dealing with arrays of byte or char, the easy/stupid/slow approach is just to convert to string
03:44 RRR2 sorear: I tried that, but when converting these bytes to strings, some bytes were lost on the converesion, somehow, so I'd just use this method
03:45 RRR2 Also, a matching subarray function will be useful anyway
03:45 sorear RRR2: you should use an encoding that maps all bytes, like latin1
04:06 ttmrichter RRR2: http://ideone.com/9KNyvS
04:06 fedaykin "Ideone.com | 9KNyvS"
04:07 ttmrichter That code finds all matching subarrays.
04:08 RRR2 nice
04:10 ttmrichter Do you need me to walk you through what it's doing?
04:15 ttmrichter RRR2: The original version of that code was very, very, very complicated and ugly.  It turns out you can program C in any language.  :D
04:17 RRR2 ttmrichter: Well, a walkthrough wouldn't be bad. I had to google a Prolog tutorial, it's blowing my mind
04:17 ttmrichter Hah!  Yeah, Prolog will sprain your brain at first.
04:18 ttmrichter OK, the entry point, obviously is subarray/3.  (That's the subarray predicate with an arity of 3.  Standard Prolog--and Erlang--notation.)
04:18 ttmrichter And Mercury too.
04:18 ttmrichter The first argument is the subarray you're looking for.  I'm breaking it into its head (X) and the rest of it (Xs).
04:18 ttmrichter So with the sample data provided it's X=4, Xs=[5,6].
04:19 ttmrichter The second argument is the array you're searching.
04:19 ttmrichter The third argument is the "output" argument which will contain the index of the match.
04:19 ttmrichter The general approach is to find the head in the main array (4, in this case) and then match the remainders.
04:20 ttmrichter So as an operational overview, I'll scan the main array for the head and get it to return the index (I) and the remainder (Ys1).
04:21 ttmrichter Then I match the remaining subarray ([5,6]) against the remainder of the main array (Ys1).  If they match, success, if they don't, fail.
04:21 ttmrichter On a failure, however, the Prolog interpreter will backtrack and try find_head/5 again, continuing forward until it finds the next matching head.
04:21 ttmrichter Then it tries match_rest/2 again and so on until either there's a full match or until it reaches the end of the main list.
04:22 ttmrichter So, now the Stupid Prolog Tricks.
04:23 ttmrichter find_head/5 has two clauses.  The first clause matches the head (X) against the head of the full array ([X|Ys]).  If the head matches, it returns the rest (Ys) and the index (I) passed in in the output parameters.
04:23 ttmrichter If the heads DON'T match (the second clause), it increments the index and then recursively calls itself with the remainder (Ys0) and the new index.
04:24 RRR2 Alright, interesting, I think I can translate it, thank you very much
04:24 ttmrichter So operationally it calls itself one array element at a time matching the head of the desired subarray.  On success it returns the remainder (for later backtracking and restarting) and the current index (for a full match).
04:25 RRR2 hmhm
04:25 ttmrichter match_rest/2 just compares heads until the subarray is out of entries at which point it succeeds.
04:25 ttmrichter Any other condition (heads don't match, main array runs out) results in a failure.
04:27 mwn3d1 RRR2: I'm starting from the beginning here...did you try iterating through the list getting sublists of the right size until you get a sublist that matches the target?
04:28 mwn3d1 ArrayList has a sublist method that could mashes it pretty clean
04:30 mwn3d1 Make* not mashes. Swype messes things up sometimes :/
04:36 sorear guessing findall is some deeply magical prolog builtin
04:39 ttmrichter sorear: Findall isn't that magical.  It's just a way of collecting all the results from a non-deterministic predicate into one container.
04:40 ttmrichter If you manually did the call to subarray it would, at the query, display Index = 10 and then wait.
04:40 ttmrichter Enter accepts that as the result, ; tells it to retry.
04:41 ttmrichter findall/3 does the same thing as you'd do manually, only it does it FOR you and it puts it into a collection for you.
04:51 sorear ttmrichter: that's what I inferred
04:52 ttmrichter Yeah, but it's not magical.  The magic comes from the runtime's backtracking and unification algorithms.  Findall just manages the magic for you.  :)
04:55 sorear I just meant that I don't think it can be expressed in terms of the most basic operations, because it requires the ability to remember information despite backtracking
05:28 ttmrichter sorear: Yeah, it's a built-in and non-logical for sure.
05:28 ttmrichter But it's very, very, very useful so we forgive it.  :)
05:29 ttmrichter sorear: That being said: http://stackoverflow.com/a/7716944/282658
05:29 fedaykin "Bad Request"
05:30 ttmrichter You can implement findall in Prolog.  It's non-logical (note the cuts), but it's possible using the core language.
05:30 ttmrichter However doing it *EFFICIENTLY* pretty much requires making it a built-in.
05:31 ttmrichter That solution there will thrash your memory but good for any complex or sizable query.
05:38 ttmrichter sorear: Here's an even uglier Prolog implementation of it:  http://ai.ia.agh.edu.pl/wik​i/pl:prolog:pllib:findall?s[]=findall
05:38 fedaykin "pl:prolog:pllib:findall [aiWiki]" http://rldn.net/ENNp
05:48 barneybook joined #rosettacode
05:56 * sorear has never actually used Prolog, but implemented a toy Prolog with unification, backtracking, recursion, predicates, and atoms in his #haskell days while playing with type inference
05:56 sorear (so those five are what I think of as the most primitive features)
05:57 sorear oooh, 'not'.  that's something outside my set that can be put to use here for sure
05:58 ttmrichter If you've implemented that toy Prolog you know enough to follow along to about 99.44% of Prolog code.
05:58 ttmrichter \+ is a trivial thing to implement.
05:58 ttmrichter It's roughly equivalent to ( Goal -> fail )
05:59 ttmrichter (Very roughly.  There's a bit more wizardy in the implementation that doesn't suppress a choice point.)
06:02 bilat ttmrichter: which programming language do you consider your greatest learning experience?
06:04 ttmrichter bilat: Tough question.  The ones I've learnt the most from are, in rough order of exposure *AND COMPREHENSION*: assemblers of various breeds, C, Forth, Prolog, Haskell and Mercury.
06:04 ttmrichter Oops.  Sorry.  Flip around C and Forth.
06:04 ttmrichter Forth first, then C.
06:09 bilat At the moment i've mostly been learning python, though I used java at university and have learnt some C and C++ in the past. I'd like to learn another language since I feel like python is good for quick solutions to problems but it doesn't seem to be a very useful learning experience.
06:14 ttmrichter bilat: All the languages you've named are imperative.  You should break out into some of the declarative paradigms if you want to change how you think.
06:14 bilat ttmrichter: do you have any recommendations?
06:14 ttmrichter Prolog or Haskell would be decent candidates.
06:33 * eMBee agrees with ttmrichter, but apart from that, python is good for much more than quick solutions
06:35 ttmrichter Yes.  It's good for finding out why Guido is an ass.  :)
06:37 eMBee explain
06:38 eMBee i mean opinions about python itself aside i see no evidence for that
06:38 ttmrichter Guido has an irrational hate-on for functional programming.  So as such he gets "persuaded" to include functional features, but then goes out of his way to make them half-assed (lambdas) to "prove" they're not useful, or he makes up really stupid excuses for why they're not desirable (c.f. his claims about TCO).
06:39 ttmrichter Unlike the Lua guys who simply and professionally state that they will not insert feature X because it does not suit their goals for the language, he actually goes out of his way to be CHILDISH about it.
06:47 eMBee ok, well, i have a different opinion about it, but anyways, thanks...
08:59 barneybook joined #rosettacode
09:50 TimToady joined #rosettacode
09:59 bilat ttmrichter: Prolog looks nice. I'm reading about it on www.learnprolognow.org
09:59 fedaykin "Learn Prolog Now!"
10:01 ttmrichter Probably one of the better ways to learn it.
10:01 ttmrichter Protip: DO THE EXERCISES.
10:01 ttmrichter Seriously.  Don't just read them and find the solutions.
10:01 ttmrichter Try them.
10:03 bilat Do you use swi-prolog?
10:04 ttmrichter Yes.
10:05 ttmrichter And YAP.  But mostly SWI.
11:53 mwn3d joined #rosettacode
13:00 mwn3d1 joined #rosettacode
14:11 timotimo joined #rosettacode
14:18 mwn3d joined #rosettacode
15:48 barneybook joined #rosettacode
17:41 BenBE joined #rosettacode
17:41 BenBE joined #rosettacode
17:48 BenBE joined #rosettacode
21:38 dduncan joined #rosettacode
21:41 dduncan left #rosettacode
23:13 mwn3d1 joined #rosettacode

| Channels | #rosettacode index | Today | | Search | Google Search | Plain-Text | summary