libera/commonlisp - IRC Chatlog
Search
6:02:52
beach
remexre: Sets are tricky things. There is really no abstract data type called a "set" because it is impossible to have all set operations be efficient simultaneously. That is why every abstract data type that contains other objects is defined by the operations that are supported. If you give us the operations you like, perhaps we can help.
6:03:22
beach
remexre: But in general, such a representation would not allow for many operations to be efficient.
6:05:14
moon-child
sorted vector gives you binary search if you care for it, but no in-place intersection or union
6:05:41
beach
remexre: For intersection, convert to lists, do the intersection, convert to a vector, sort.
6:07:11
beach
That sounds like premature micro-optimization without any measure to determine whether it is necessary.
6:07:51
beach
remexre: You are comparing cache effects and asymptotic complexity. They are not the same order of magnitude.
6:08:29
beach
remexre: My guess is that you are going to spend all the time comparing characters in strings anyway.
6:09:05
moon-child
beach: 'For intersection, convert to lists, do the intersection, convert to a vector, sort' hmm? If you were using such a representation--and you cared for performance--you could do it in O(m+n) by iterating over both vectors and VECTOR-PUSH-EXTENDing a result
6:09:18
moon-child
(and if you don't care for performance, just use a list and don't bother with anything else)
6:09:43
remexre
the point with the asymptotics was that they're not terrible; not ruining the cache by using vectors was more of the point
6:10:55
moon-child
sure. I think the problem is insufficiently motivated/contextualized. If it's desirable for some reason to use a vector in the first reason, that same reason may also make it undesirable to use an intermediate list (which was your suggestion)
6:11:55
moon-child
given two sorted vectors, you can produce a sorted intersection vector in linear time, without consing an intermediate list and calling SORT on it
6:12:33
moon-child
yes. And if it doesn't matter then you can just use lists. We are going in circles :P
6:13:46
moon-child
remexre: can you motivate your problem? Do you have set-processing code which is slow?
6:14:09
remexre
no, I'm planning on writing code that I don't want to go back and change the set representation for
6:14:46
moon-child
if your interface is properly abstracted, it should not be prohibitively difficult to change your representation
6:16:04
remexre
right, but i know the representation I want, and I would be surprised if I needed to change *from* that later
11:02:31
neominimum
Anyone have a more elegant solution to finding the first element of a list and all sub-lists than what I have managed to hack together? https://pastebin.com/raw/6W6ppPTb
11:18:49
flip214
We've got a CI/CD pipeline for Alexandria now. Are there volunteers for finding out why some implementations disagree with the majority? https://gitlab.common-lisp.net/alexandria/alexandria/-/jobs shows 4 of 8 failing (in overlapping sets of tests).
11:56:10
phoe
I have no idea if this is conforming, because the complex number has different types for realpart and imagpart
11:57:59
phoe
no idea about cmucl and allegro - cmucl complains about some undefined function, which is weird, and acl has some type failures as well as a copy-hash-table failure
12:06:43
flip214
phoe: (EQUAL #C(0.0 0.0) 0.0) -- That's what my testing branch shows as difference. Looks like clisp doesn't see them as EQL...
12:19:19
specbot
Rule of Canonical Representation for Complex Rationals: http://www.lispworks.com/reference/HyperSpec/Body/12_aec.htm
12:20:31
phoe
if I am reading this correctly, if their parts are floats, then they are not meant to be EQL
12:29:25
flip214
phoe: https://gitlab.common-lisp.net/alexandria/alexandria/-/jobs/27975 (allegro) has the same subtypep problems
12:30:41
flip214
http://www.lispworks.com/documentation/HyperSpec/Body/f_eql.htm#eql says " If an implementation supports positive and negative zeros as distinct values, then (eql 0.0 -0.0) returns false. Otherwise, when the syntax -0.0 is read it is interpreted as the value 0.0, and so (eql 0.0 -0.0) returns true."
12:34:14
flip214
pjb: I don't understand where you get the ε from - the zero can be expressed exactly (though perhaps non-unique because of ±), and so 0.0 == 0.0??
12:35:01
flip214
https://gitlab.common-lisp.net/alexandria/alexandria/-/pipelines/5874 shows that 4 implementations were okay with (EQUAL #C(0.0 0.0) 0.0)
12:36:09
flip214
pjb: http://www.lispworks.com/documentation/HyperSpec/Body/f_eql.htm#eql has the example (eql 3.0 3.0) => true
12:36:45
flip214
http://www.lispworks.com/documentation/HyperSpec/Body/f_equal.htm says if they are numbers that are eql,
12:38:42
pjb
This is precised in the Note: Two complex numbers are considered to be eql if their real parts are eql and their imaginary parts are eql. For example, (eql #C(4 5) #C(4 5)) is true and (eql #C(4 5) #C(4.0 5.0)) is false. Note that while (eql #C(5.0 0.0) 5.0) is false, (eql #C(5 0) 5) is true. In the case of (eql #C(5.0 0.0) 5.0) the two arguments are of different types, and so cannot satisfy eql. In the case of (eql #C(5 0) 5), #C(5 0)
12:45:01
neominimum
beach: ah yes, that was intentional. removing `(atom (caar form))` prints (1 2 3)
12:45:32
beach
neominimum: The form (and root (print (car form))) is better written as (when root (print (car form)))
12:48:07
beach
neominimum: I also don't understand what ROOT is there for. It is only true for the top-level expression.
12:49:34
yitzi
beach: Lots of non-interesting real life distractions. Trying to get back into the groove though. I am still seeing that SICL issue I mentioned about a month ago, but I made some progress on isolating it. I'll bug you when I have something useful and you have time. :)
12:49:45
neominimum
I was stumped trying to print the root of the tree in the same recursive function that returns the first elements of all sub-lists
12:50:01
beach
neominimum: And I think (and form (listp form)) is just (consp form) which has the additional advantage of not using arbitrary lists as Boolean values.
12:52:15
beach
neominimum: Also, it would be better to return a list of the objects you want, rather than printing them. That way, client code can print them, or do something else with them. Right now, they are useless.
12:54:39
neominimum
beach: sure, I was only printing them so that I could tell that the appropriate elements were being isolated.
12:54:50
beach
neominimum: And I think you should be able to have the base case of the recursion be simpler.
12:56:03
beach
So I don't understand why you omitted (1 2 3) because that was not part of your specification.
12:56:54
beach
Is the specification to "return/print the first element of each sublist, provided it is an atom"?
12:57:32
beach
Er, "return/print the first element of each non-empty sublist, provided that element is an atom"
13:03:07
beach
The recursion on the CDR is fundamentally different from the recursion on the CAR it seems. So I would either use different functions for the two, or use LOOP instead of recursion on the CDR.
13:13:17
beach
(defun tt (thing) (if (atom thing) '() (append (if (atom (car thing)) (list (car thing)) '()) (loop for element in thing append (tt thing)))))
13:22:18
neominimum
Oh nice, thanks beach for the example. It's good to see how you approach the solution.