On 27 March 2015 at 03:30, Ralf Hemmecke <[email protected]> wrote: > > Well.. If we drop SetCategory from Key, then the documentation must be > rewritten in some places. I strongly oppose if just the new function is > committed without changing the appropriate places in the whole > documentation, i.e. the part inside )if LiterateDoc ... )endif.
Of course I will update the documentation but not without first complaining that the current situation with )if LiterateDoc ... )endif and elsewhere )if LiterateDoc ... )endif in about 10 other SPAD files seems like a mess to me. Code embedded in a lot of text, i.e. noweb, was bad enough but now we have a lot of text embedded in code and that seems even worse. Although I do appreciate having the documentation available, but my first reaction was to start by deleting everything between )if LiterateDoc ... )endif so I could actually read the code in a reasonably concise form. Do we still have a way to produce pdf or dvi files from these "literate" source documents? Now that we have removed the empty noweb boilerplate from most of the SPAD files wouldn't it make sense to introduce a new directory, say src/doc/algebra, and put the available documentation source files there in an easily rendered LaTeX format? In other words we would have both 'src/algebra/xhash.spad' and 'src/doc/algebra/xhash.tex'. Yes I know that in order to keep exactly the same documentation content we had before with noweb we would have to copy some or all of the code into verbatim or listing sections in the LaTeX file, but to me that would be greatly preferable to the way it is now. > > I have created XHashTable simply because the original Table was not > taking care of =$Key and resorted to AssociationList. I haven't looked > now, but the documentation certainly has some places that refer to > equality from Key. > OK. > Furthermore, deviating from > > if eq(a, b) then hash(a) = hash(b) > > might yield unpredictable results. Maybe not for insertion and > searching, but it should be checked carefully what happens when > > not eq(a,b) and hash(a) = hash(b) > > when a or b is deleted from the table, because deleting a might result > in actually removing b from the table. > I do not intend to deviate from if eq(a, b) then hash(a) = hash(b) I agree that that is an essential part of the definition of hash function. In the existing XHashTable code if an incompatible hash function is passed the almost immediate result is an array bounds failure in the 'rehashAux!' routine due to an unexpected duplicate key. A simple change in 'localSearch' to check both hash and eq, for example: hk := h k h1: Z := hk::Z ... hk = h toKey mk and eq(k,toKey mk) => return p -- key found ... not deleted? mk and hk = h toKey mk and eq(k,toKey mk) => is sufficient to prevent this and maybe preferable since usually calling hash is much cheaper than computing eq even when eq defaults to =$Key. Since evaluation of 'and' is lazy I guess the mileage will depend on the statistics of hits and misses. > OK, if Bill requires > > if not eq(a,b) then hash(a) ~= hash(b) > > that's not an issue, but still. There should be a thorough revision. I suppose that you meant to write: if Bill requires: if hash(a) ~= hash(b) then not eq(a,b) This is logically equivalent to what you already wrote in the documentation but I wrote it this way to emphasize this requirement on the new eq function argument. > > If Bill then uses as eq for Expression that builds on smaller?, i.e. > Comparable, I also oppose. Comparable is there for some technical > reason. It's an arbitrary total order on a (maybe non-totally ordered) > domain. Ralf, I think you really need to check the details here. At this level all reasons are "technical". > Technically, Bill's idea is probably OK, but here again it comes > to my mind to build Expression(X) as a wrapper domain of underlying > ExpressionRep domains that have equality according to their > representation, i.e. only equal (via =) if rep is equal. Doing this > would also avoid having to change XHashTable, btw. And I guess > using = from ExpressionRep would be faster than checking > > not smaller?(x, y) and not smaller?(y, x) > Why do you expect = in Rep to be equivalent to not smaller?(x, y) and not smaller?(y, x) But I do agree that there are more efficient ways to compute this sort of equality that calling 'smaller?' twice (in the worst case). I'll say more about why I think 'Comparable' is important when I get a chance to reply to Waldek but for now let's just agree that passing an additional parameter to 'table()$XHashTable' is not so bad. Bill. -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
