slburson / fset Goto Github PK

Hello Scott,

This question is certainly more general than FSet, but I thought it would be interesting to put this concrete use case in practice.

The problem is simple: let's take for example an ordered collection of stock quotes (a stock quote is a structure consisting of a date and a value) and draw a chart from them, the date on the abscissae and the value on the ordinates. Then I would like to lookup which pair of stock quotes falling under my mouse pointer.

For this, I could simply search the collection and find the interval. I have read that a binary search is a simple and fast solution.

Is there in FSet a data structure that readily provides an answer to this problem? I was thinking about wb-trees but I'm afraid this is too low level. What do you think?

Thank you very much in advance!

Cam

count-if and count-if-not on a set return nil :
(fset:count-if #'evenp (fset:convert 'fset:set (list 1 2 3)))
NIL

In count-if, "returning" n is done inside do-set (twice).

I think the same problem exists with bags, maps and seqs

Normally, reversing a sequence reverses it:

CL-USER> (fset:reverse (fset:seq 1 2 3 4))
#[ 4 3 2 1 ]

But if the elements of the sequence are characters, reverse fails:

CL-USER> (fset:reverse (fset:seq #\a #\b #\c #\d))

Results in the condition:

The value
  "abcd"
is not of type
  FSET::WB-SEQ-TREE-NODE
   [Condition of type TYPE-ERROR]

Backtrace:
  0: (FSET::WB-SEQ-TREE-REVERSE "abcd")
  1: ((:METHOD FSET:REVERSE (FSET:WB-SEQ)) #[ #\a #\b #\c #\d ]) [fast-method]
  2: (SB-INT:SIMPLE-EVAL-IN-LEXENV (FSET:REVERSE (FSET:SEQ #\a #\b #\c #\d)) #<NULL-LEXENV>)
  3: (EVAL (FSET:REVERSE (FSET:SEQ #\a #\b #\c #\d)))
 --more--

I'm using SBCL 2.1.1 with fset-20200610-git from Quicklisp, in case that makes a difference.

It gets pretty hard to use multiple libraries that extend the readtable without using named-readtables. I will be writing up a named-readtable for fset anyway. I can submit a pull request if that is something people would be interested in.

The default map syntax is too complicated and makes working with nested maps needlessly difficult. Compare:

#{| (:CHILD #{| (:CHILD #{| (:CHILD NIL) |}) |}) |}

with the equivalent clojure:

{:child {:child {:child nil}}}

)|})|})|} vs }}} is a no-contest in terms of convenience and readability, especially considering that I'll probably be working with structures with quite a bit more nesting than just 3 levels.

I'm planning on overriding print-object and modifying the read-table in my own project for my own convenience without modifying FSet. My question is would my design, if it were implemented in a backwards compatible way, be acceptable upstream? I'm currently thinking of something like this:

#M{:child #M{:child #M{:child nil}}}

With possibly a special variable to control how the maps should be printed.

Please consider adding :description, :author and :license information to your ASDF system(s). This will greatly help Quicklisp users and make it easier for them to report bugs.

More information:

http://blog.quicklisp.org/2015/05/looking-for-more-metadata.html
https://www.quicklisp.org

(equalp (intersection (convert '2-relation '((1 . 2))) (convert '2-relation '((1 . 3)))) (empty-2-relation)) ==> NIL

The problem is the representation for the intersection maps 1 to an empty set, but this pair should have been removed from the tree, as it causes EQUAL? to indicate they are not the same.

Paul ran into this; see 9810f53 (reverted in 84a734f). Racking my brain to try to remember whether there was any specific reason I might have done this intentionally; it seems obvious that the defaults should be checked. But I don't yet recall any such reason.

On CL sequences, lookup is just defined as elt, which means that unlike all the other definitions of lookup it doesn't return a second value of T on success.

When asdf:load-ing fset I see the following:

; file: /home/sly/quicklisp/local-projects/fset/Code/fset.lisp
; in: DEFMETHOD FSET::SORT-AND-GROUP (FSET:SEQ T)
; (FSET:DO-SEQ (FSET::X FSET::SORTED)
; (IF (OR (FSET:EMPTY? FSET::GROUP)
; (NOT
; (IF FSET::KEY
; #
; #)))
; (FSET:PUSH-LAST FSET::GROUP FSET::X)
; (PROGN (FSET:PUSH-LAST FSET::RESULT FSET::GROUP) (SETQ FSET::GROUP #))))
;
; caught STYLE-WARNING:
; undefined function: FSET:DO-SEQ

; (FSET:SEQ)
;
; caught STYLE-WARNING:
; undefined function: FSET:SEQ

; (FUNCALL FSET::KEY FSET::X)
; ==>
; (SB-C::%FUNCALL (SB-KERNEL:%COERCE-CALLABLE-FOR-CALL FSET::KEY) FSET::X)
;
; caught WARNING:
; undefined variable: FSET::X

; (FSET::X FSET::SORTED)
;
; caught STYLE-WARNING:
; undefined function: FSET::X
;
; compilation unit finished
; Undefined functions:
; FSET:DO-SEQ FSET:SEQ FSET::X
; Undefined variable:
; FSET::X
; caught 1 WARNING condition
; caught 8 STYLE-WARNING conditions

The problem is that the SEQ and DO-SEQ macros aren't yet loaded. There are some order dependencies that make fixing this a little bit tricky but I imagine it's relatively straightforward.

The UPDATE operator is designed to take a symbol (naming a function) as the first argument. However, this fails because @ does not recognize a symbol as a function, but instead tries to call lookup on it.

(@ #'- 3) ==> -3
(@ '- 3) ==> should be -3, but signal an error

is there a reason why the symbols (:some :every :notany :notevery) are not exported?

Copied from trac.common-lisp.net/fset, issue 2, filed 2007-06-11.

Review the test suite to see if there are any interfaces that are not tested (there are probably a few). Add tickets here for any you find.

ECL fails as:

The function FSET::MAKE-CHAR is undefined..

and CLisp was a bit different:

:info:test *** - Test failed:
:info:test        (NEW-LET:LET
:info:test         ((FSET::HT
:info:test           (FSET:CONVERT 'HASH-TABLE (FSET:MAP (1 2) (3 4)) :TEST 'EQUAL)))
:info:test         (EQL (HASH-TABLE-TEST FSET::HT) 'EQUAL))

and ABCL is also different:

:info:test ; Compilation unit finished
:info:test ;   Caught 1 WARNING condition
:info:test Caught UNBOUND-VARIABLE while processing --eval option "(asdf:operate (quote asdf:test-op) (quote fset))":
:info:test   The variable LIST-17623 is unbound.

Personally, I'd much prefer absolute position, for consistency both with cl:position and across fset:position's methods.

(fset:position #+ (fset:convert 'fset:seq "---+---+---") :start 4)
=> 3
(fset:position #+ "---+---+---" :start 4)
=> 7

The iterate package allows extensions to be defined for iterating over new kinds of data structures. Add extensions that operate on specific fset datatypes, as well as a generalized combination of these (and other non-fset sequence) types. These extensions should go into a separate system fset/iterate so they don't get loaded (pulling in iterate) when not needed.

Copied from trac.common-lisp.net/fset issue 4, filed 2007-06-11.

The CL compatibility functions (that is, the generic versions of the CL sequence functions -- find etc.) need to be tested in the test suite. (I have hand-tested them, but a test that could be re-run after changes would be better.)

Hello Scott,

I recently discovered FSet, and I am looking forward to use the clean and easy to understand concepts your library offers.

I read the documentation, it is very complete, thank you so much for doing that! It would be really nice if you could include the documentation right in the git repository, so it can be read while being offline, or not worrying about the website availability of common-lisp.net. Also it would offer the possibility to see the changes made to the documentation, if any (it is already very complete).

Regarding the documentation, I would like also to ask you if you could add a small paragraph about multi-processing. I read an old discussion between Rich Hickey and Pascal Costanza about an implementation he made of the Ants Clojure example. This discussion made me curious about the FSet project, and while I understand the benefits regarding multi-processing, I would like to know more about this aspect.

Finally, I am intrigued about dynamic tuples. I understand the example you give in the extended documentation page, but I have difficulty to find a real-life example of this.

Thank you again for this fine library.

Camill

Copied from trac.common-lisp.net/fset issue 3, filed 2007-06-11.

Tuples are the only FSet datatype whose implementation involves shared data structures. A multithreaded test is in order.

Hello,
Evaluating the following returns false instead of 53:

(lookup (map (#C(5 16) 41)
             (#C(-4 15) 43)
             (-8 52)
             (-9 53)
             (#C(14 8) 42))
        -9)

Whenever I load a project that depends on Fset, I get the following warning:

.quicklisp/dists/quicklisp/software/fset-20200427-git/Code/fset.lisp:1:1:
  style-warning: 
    Generic function FSET:ITERATOR clobbers an earlier FTYPE proclamation
    (FUNCTION (T &KEY &ALLOW-OTHER-KEYS) (VALUES FUNCTION &REST T)) for the same
    name with (FUNCTION (T &KEY &ALLOW-OTHER-KEYS) *).

In at least one place (lastcons/head/tail) I put a second inline declaration after the defuns it applies to, in addition to the one that precedes them. My recollection is that there are implementations that don't honor the declaration unless it follows the defun, although the more common behavior is the other way around. Alas, I don't recall which implementations want it which way. To top it off, at least one implementation (SBCL?) that wants the declaration first will issue a style warning when it finds another one later.

So the tasks here are:

• test the various implementations to see which order they accept
• define features inline-before-defun and inline-after-defun which are set appropriately
• make sure all inline declarations appear both before and after their defuns, with the appropriate conditionalization in each case
• consider recommending to implementors that, given the standard's vagueness on this point, implementations should accept either order without complaint

I'm using @ as funcall, and this doesn't work well with functions not taking any arguments.

; in: DEFUN LEARNER
;     (FSET:@ (MANG::MATCH-EVERYTHING-GENERATOR))
; --> NEW-LET:LET LET IF 
; ==>
;   (FSET:LOOKUP #:FN-0)
; 
; caught STYLE-WARNING:
;   The function was called with one argument, but wants exactly two.

I think reimplementing @ like this should fix the problem, since lookup takes 2 arguments either way:

(defmacro @ (fn-or-collection &rest args)
  "A little hack with two purposes: (1) to make it easy to make FSet maps
behave like Lisp functions in certain contexts; and (2) to somewhat lessen the
pain of writing higher-order code in a two-namespace Lisp like Common Lisp.
The idea is that you can write `(@ fn arg)', and if `fn' is a Lisp function,
it will be funcalled on the argument; otherwise `lookup' (q.v.) will be called
on `fn' and `arg'.  To allow for `@' to be used in more contexts, it actually
can take any number of `args', though `lookup' always takes exactly two.  Thus
you can write `(@ fn arg1 arg2 ...)' when you just want a shorter name for
`funcall'.  As a matter of style, it is suggested that `@' be used only for
side-effect-free functions.  Also, though this doc string has spoken only of
FSet maps, `@' can be used with any type that `lookup' works on.  Can be used
with `setf', but only on collections, not functions, of course."
  (if (or (not args)
          (> (length args) 1))
      ;; Hmm.  We _could_ listify `args' and use that as the map key.
      `(funcall ,fn-or-collection . ,args)
    (let ((fn-var (gensym "FN-")))
      `(let ((,fn-var ,fn-or-collection))
	 (if (functionp ,fn-var)
	     (funcall ,fn-var . ,args)
	   ;; We do it this way rather than just `(lookup fn-or-collection (car args))'
	   ;; so that we get the right error when `args' is not of length 1.  If this
	   ;; doesn't get compiled well everyplace we care about, we could test the
	   ;; length and issue the error ourselves (if that helps).
	   (lookup ,fn-var . ,args))))))

http://report.quicklisp.org/2014-12-26/failure-report/fset.html has a compile log - I can't build fset today as a result.

; caught WARNING:
;   The function was called with two arguments, but wants exactly one.

Hi,

The Readme file mentions a page that seems no longer available.
Also content about FSet is a bit spread on several pages (tutorial, FSet-CL page, ...).

I would be happy to add this documentation to the Github's Wiki.
Let me know!

Cam