IRC channel logs


back to list of logs

***Server sets mode: +nt
***Ekho- is now known as Ekho
***sneek_ is now known as sneek
<manumanumanu>Is there any b-tree implementation for guile? I need an ordered map, and my old b-tree implementation is lost to the sands of time (and my current Red-Black tree is for some odd reason very very slow. 2 seconds to add 10k elements is pretty bad).
<amirouche>in-memory or on-disk?
<amirouche>manumanumanu: ^
<amirouche>anyway, I do not know on-disk b-tree implementation using scheme (I am very interested to find one!)
<amirouche>otherwise there is
<amirouche>mit/scheme and SCM have a well balanced binary trees
<chrislck>how would one define a (define (xor a . rest) ...) recursively for an arbitrary number of arguments? Note logxor handles unlimited args.
<chrislck>something better than (define (xor . args) (not (zero? (apply logxor (map (lambda (elt) (if elt 1 0)) args)))))
<lloda>(define odd? (compose not even?))
<lloda>(import (srfi :1))
<lloda>(define (xor . a) (odd? (count identity a)))
<lloda>I think?
<flatwhatson>(define (xor . args)
<flatwhatson> (let loop ((ls args) (res #f))
<flatwhatson> (cond ((null? ls)
<flatwhatson> res)
<flatwhatson> ((and res (car ls))
<flatwhatson> #f)
<flatwhatson> (else
<flatwhatson> (loop (cdr ls) (or res (car ls)))))))
<flatwhatson>chrislck: ^^
<chrislck>cool. any takers, eg case-lambda magic?
<civodul>lloda: (negate even?) looks nicer than (compose not even?), and it's also a bit more efficient (one less procedure call)
<lloda>fair fair
<lloda>it's simple enough that i'd write (not (even? (count ...))) prolly
<lloda>but it's peculiar that even? is defined and odd? isn't
<civodul>it's odd, even
<civodul>actually odd? is defined
<civodul>or is that an R6 issue?
<lloda>oh it is
<lloda>i think i tried odd and not odd? and then I defined odd? which is odd
<lloda>they are in (guile) even
<chrislck>you're even then
<chrislck>flatwhatson: (logxor 1 0 1 0 1) -> 1, but your (xor #t #f #t #f #t) => #f
<flatwhatson>chrislck: Yeah I implemented "Exactly one of these things must be true" instead of "An odd number of these things must be true", it seemed sensible.
<lloda>logxor is 'A bit is set in the result if it is set in an odd number of arguments.'
<lloda>but i'd agree that makes more sense as 'exclusive or'
<lloda>then you could do (define (xor . a) (any identity a))
<flatwhatson>Then you'd get (xor #t #t) => #t
<lloda>right :-/
<lloda>(= 1 (count identity a)) then
<lloda>(logior) is 0
<flatwhatson>Yes, but and/or return the last truthy input instead of #t, which is often useful.
<lloda>(import (ice-9 match) (srfi :1))
<lloda>(define (xor . a) (match (find-tail identity a) (#f #f) ((x . rest) (and (not (any identity rest)) x))))
<dsmith-work>Wednesday Greetings, Guilers
<flatwhatson>lloda: Nice! Now this one:
<flatwhatson>(define (xor . args)
<flatwhatson> (let loop ((ls args) (r #f) (n 0))
<flatwhatson> (cond ((null? ls) (and (odd? n) r))
<flatwhatson> ((car ls) (loop (cdr ls) (car ls) (1+ n)))
<flatwhatson> (else (loop (cdr ls) r n)))))
<rekado_>I would replace the car and cdrs with a match expression
<wingo>are we golfing? :)
***Aurora_iz_kosmos is now known as Aurora_v_kosmose
<wingo>(use-modules (srfi srfi-1))
<wingo>(define (xor . args)
<wingo> (fold (lambda (arg res)
<wingo> (if arg (not res) res))
<wingo> #f
<wingo> args))
<flatwhatson>Very neat, but it doesn't return the last truthy value
<wingo>ah indeed.
<wingo>i guess s/not res/if res #f arg/
<chrislck>ah the master
<chrislck>we're O(small)ing
<chrislck>fold is underrated...
<chrislck>thanks boss!
<dsmith-work>I was going to suggest a fold. No really, I was..
<lloda>fold always runs over the whole list. For xor = only one, you don't need that
<dsmith-work>So what should the value be with no args? One? Does that even make sense for XOR ?
<lloda>(logior) returns 0, so (xor) should return #f
<lloda>(or) returns #f which makes sense
<lloda>ie 'zero' != 'exactly one' so #f
<dsmith-work>s/One?/One arg?/
<lloda>same as (or)
<lloda>sorry (xor a) = (or a)
<manumanumanu>amirouche: that one from adam is exactly what i'm looking for. Not on disk, as you might guess :)
<lloda>i like the exactly one definition, wonder why logior is defined like that
<flatwhatson>The "odd" thing is because that's how (xor a (xor b c)) behaves
<manumanumanu>amirouche: it looks portable enough, and porting schemepunk to guile seems rather straightforward.
<dsmith-work>"schemepunk" sounds like a genra of fiction
<amirouche>I like the name
<manumanumanu>amirouche: and the srfi-166 implementation seems a lot more efficient than the reference implementation. basing it on generators seems like a generally good idea
<amirouche>I never touched srfi-166, even if I like the idea.
<manumanumanu>srfi-166 is, hands down, the nicest string format utility I have ever used.
<manumanumanu>I had a compiler for it, that compiled the (ice-9 format) subset of it to more efficient scheme. it was lost in a fire though
<manumanumanu>I have thought about writing an implementation for it for guile.
<manumanumanu>not based on the reference implementation (which uses call/cc for the columnar formatting)
<manumanumanu>which schemepunk show does not.
<manumanumanu>but it uses it for some of the trimming formatters
<manumanumanu>which seems odd
<amirouche>Arthur published a Post Finalisation Note (PFN) SRFI-167 (okvs) and SRFI-168 (nstore), saying do not use them, among many problems those SRFI have, there is one I could not avoid: ALL okvs libraries made the same mistake sheeping the original BerkeleyDB design, I asked the maintainer why it was not possible to count the number of keys, they replied: it is a design mistake
<amirouche>=> next iteration on okvs will have that procedure, that makes coding query optimizer much more easy.
<amirouche>That is why I need an on-disk b-tree (even if it will be slow)
<amirouche>at least the design will be correct, and *maybe* people will start adding the function in their C implementations.
<manumanumanu>Correction: the reference implementation stopped using call/cc for columnar formatting, and things look like they could be faster!
<amirouche>key count allows to implement key subspace statistics.
<amirouche>manumanumanu: some implementation have fast call/cc faster than Chez IIUC.
<amirouche>SRFI-180 should use make-coroutine-generator, it is much more readable.
<amirouche>the code without call/cc was a pain to write, and I guess a pain to read, it is manual CPS.
<samplet>Does Guile offer a way to do locale-dependent character classification?
<samplet>SRFI 14 (char-sets) is locale-independent, and I don’t see anything in section 6.25 (Internationalization) of the manual.
<dongcarl>Hi all, if I have guile packages in my /usr/local prefix, is it enough to just do GUILE_LOAD_PATH=/usr/local/share/guile/site or do I have to do the full GUILE_LOAD_PATH=/usr/local/share/guile/site/2.2 ?
***Noisytoot is now known as []{}\|^`-
***[]{}\|^`- is now known as Noisytoot
***Noisytoot is now known as ||||||
***|||||| is now known as Guest7851
***Guest7851 is now known as Noisytoot
<manumanumanu>amirouche: the only implementations where call/cc is fast is cheney on the MTA based where call/cc is free. They are all slower than chez, though :D Anyway, the delimited continuations you can get in chez if you go under the hood are a lot faster than both call/cc and call/cc1 in chez.
<wingo>good evening
<amirouche>manumanumanu: by the way, why do you favor b-tree instead of a binary tree?
<manumanumanu>better cache locality
<manumanumanu>a left-leaning red black tree is simpler to implement, but whatever I hacked together a couple of days ago is too slow because I fudged something
<amirouche>I guess I will go with scheme punk b-tree, it will be less work.
<amirouche>the thing is that implementation will run in the browser, so i do not know how cache localit works in that setting.
<manumanumanu>if you have access to srfi-146, the non hashing one is a red-black tree
<leoprikler>samplet, what would locale-dependant classification look like?
<leoprikler>[also would it be impractical to first convert those characters to UTF-8 and classify them after the fact?]
<samplet>leoprikler: When I ask (for example) if a character is a digit, it should tell me the answer according to LC_CTYPE.
<leoprikler>I think there are some locale-dependent regular expressions somewhere (e.g. for detecting yes/no), but I forgot where and I don't think they do numbers
<leoprikler>See (guile)Accessing Locale Information
***Noisytoot is now known as ihatecoronaandih
***ihatecoronaandih is now known as Noisytoot