idf: lazy, incremental dataflow elisp library package

[https://github.com/lordpretzel/idf](https://github.com/lordpretzel/idf) Library for incremental dataflows in emacs. This library let's you construct dataflow graphs called data frames, i.e., computations on collections that can be evaluated lazily (on demand) and whose results can be materialized. The materialized versions can then be incrementally maintained, i.e., you provide inserts and deletions for the data sources processed by a dataflow graph and `idf` will update the results of the dataflow based on the changes to the input data sources (what elements got inserted and deleted from the data sources). The rationale is that is you have some large sorted list or hashtable that is the result of a non-trivial computation, it is faster to incrementally maintain the datastructure using idf if there are only small changes to the input of the computation than to recompute the full datastructure on every input change. ## Example (require 'idf) ;; create a datasource (a list of plists). In this case from a given list. (setq mysource (idf-create-source :name :seqlist :content (--map `(:x ,it :y ,(/ it 1000)) (number-sequence 1 10000)) :schema '(:x :y))) ;; now let's filter out some plists and then aggregate grouping by :y and materialize the result (setq myresult (idf-materialize-as (idf-aggregate (idf-filter mysource :expr '(and (> $x 5) (< $x 9950))) :group-by '(:y) :aggs '((sum :x)) :schema '(:y :sx)) :viewtype 'sortedlist :sortkeys '(:y))) ;; or if you prefer threading: (require 'dash) (setq myresult (-> mysource (idf-filter :expr '(and (> $x 5) (< $x 9950))) (idf-aggregate :group-by '(:y) :aggs '((sum :x)) :schema '(:y :sx)) (idf-materialize-as :viewtype 'sortedlist :sortkeys '(:y)))) (idf-mv-get-result myresult) ;; the result is this list: ((:y 0 :sx 499485) (:y 1 :sx 1499500) (:y 2 :sx 2499500) (:y 3 :sx 3499500) (:y 4 :sx 4499500) (:y 5 :sx 5499500) (:y 6 :sx 6499500) (:y 7 :sx 7499500) (:y 8 :sx 8499500) (:y 9 :sx 9000775)) ;; maintain the result when :seqlist is updated (by inserting plists) (idf-maintain myresult `(:seqlist ,(idf-delta-create :inserted '((:x 1000 :y 8) (:x 1000 :y 10))))) ;; this returns a delta for the result: #s(idf-delta ((:y 10 :sx 1000) (:y 8 :sx 8500500)) ((:y 8 :sx 8499500))) (idf-mv-get-result myresult) ;; the updated results: ((:y 0 :sx 499485) (:y 1 :sx 1499500) (:y 2 :sx 2499500) (:y 3 :sx 3499500) (:y 4 :sx 4499500) (:y 5 :sx 5499500) (:y 6 :sx 6499500) (:y 7 :sx 7499500) (:y 8 :sx 8500500) (:y 9 :sx 9000775) (:y 10 :sx 1000)) ;; we also deal with deletions (idf-maintain myresult `(:seqlist ,(idf-delta-create :deleted '((:x 900 :y 0) (:x 1000 :y 10))))) ;; the result delta: #s(idf-delta ((:y 0 :sx 498585)) ((:y 10 :sx 1000) (:y 0 :sx 499485))) (idf-mv-get-result myresult) ;; the updated result: ((:y 0 :sx 498585) (:y 1 :sx 1499500) (:y 2 :sx 2499500) (:y 3 :sx 3499500) (:y 4 :sx 4499500) (:y 5 :sx 5499500) (:y 6 :sx 6499500) (:y 7 :sx 7499500) (:y 8 :sx 8500500) (:y 9 :sx 9000775))

Inspired by differential dataflow?

Thanks! ~~The only code block formatting method which [works for all users](https://reddithelp.com/hc/en-us/articles/360043033952-Formatting-Guide#wiki_code_blocks_and_inline_code) of reddit is to switch the reddit editor to markdown mode* and indent the code by 4 spaces (you can use `M-4 C-x C-i` on a region followed by `M-x untabify` to achieve this in Emacs); and you need to use empty lines to separate the indented lines from the other text. Otherwise for lots of readers your message looks like this: https://old.reddit.com/r/emacs/comments/xkqp8q/idf_lazy_incremental_dataflow_elisp_library/~~ ~~Be sure to remove any different syntax intended for formatting (such as triple backticks) at the same time.~~ ~~(*) Switching to the markdown editor may or may not still be necessary. At one time it prevented problems.~~

fixed. I'm not posting often on reddit, so wasn't aware of their markdown limitations.

hehe, differential dataflow's claim to fame is to do incremental computation for iterative dataflows which idf does not support (currently).

This is very interesting. I've been thinking about using an AVL tree in [Ement.el](https://github.com/alphapapa/ement.el) for the lists of events in each room, because they need to be used in-order by timestamp, and they can be received in any order (e.g. when loading older events), and it wouldn't be good to re-sort the whole list after each insertion. As it stands, each event is effectively sorted at the time it's inserted into a room's buffer (which may be never, depending on whether the room has an open buffer), and it works well enough, but I wonder if it could be improved. Ideally, I would love to see some kind of integration between something like `idf` and `ewoc`, so that when new elements are added to a data collection, the UI representation could be updated in an efficient way, keeping the elements in order. I see that you mention mostly supporting plists. It would be helpful if structs/records were supported, as that's what I use for events in Ement (i.e. each event is made into a struct). Also, I hope you'll consider submitting this to GNU ELPA when it's ready. It would be great to have something like this as part of Emacs.

for your specific use case in emet, I am using this: [https://github.com/lordpretzel/sorted-list.el](https://github.com/lordpretzel/sorted-list.el) to maintain a sorted list (that is transparently backed by an AVL-tree) to enable this with O(log n) insert / deletion. This works with any list not just plists. I like the idea of using idf to update a UI view. It would be possible to extend idf to support other types of list elements. I think the right way to go would be to add a type to the data frames and then encapsulate access to fields to enable to have different types of elements to be plugged in without having to reimplement all operations for all types of possible list elements. Some of the DF operations like \`idf-map\` and \`idf-reduce\` and \`idf-filter\` already work for non-plists, but of course it would be nice to also support more "structured" operations like project or aggregate. I would like to submit this to ELPA. The only concern is that I do not know whether I will have the time to be a maintainer for this.