Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript
  • (sample set is sorted)
  • add one element to the sample set
  • recompute the IQM

LISP programmers

know the value of everything

and the cost of nothing.

But also:

  • customize via generalized reductions a.k.a. "meters"
  • a monoid and a "measure" fn
  • monoid = identity value and an associative binary operator

IQM, Finger Trees

and

Composable Incremental Computation

(in) Trees

finger trees

Bill Burcham

@billburcham

bill.burcham@gmail.com

https://github.com/Bill

a finger tree

“Imagine taking hold of the end nodes of the

example tree above and lifting them up together.”

— Hinze and Paterson

IQM/IIQM

Well I tried it anyway

  • tree but…
  • O(n) access, add at either end

(a first hack)

the interquartile mean

https://github.com/Bill/iiqm-clj

And I Learned…

But…

  • you gotta implement a full-blown type for every specialization
  • your specializations aren’t composable

but…

…maybe they could be! (next time?)

  • Clojure (FP) really did make me think different  
  • finger trees, are really flexible and useful
  • their double-ended nature is cool
  • but customization via meters is even cooler—and it's applicable to any tree, not just finger ones

Boxplot (with quartiles and an interquartile range) and a probability density function (pdf) of a normal N(0,1σ2) population

Types and Protocols

and Records Oh My!

but trees kinda suck

IQM https://en.wikipedia.org/wiki/Interquartile_mean

the incremental interquartile mean

  • counted-sorted-set is over 120 LoC
  • your-type-here will be that big
  • reuse a "non-trivial" challenge
  • O(n) indexed access
  • customize behavior via cut and paste

The finger tree paper by Hinze and Paterson:

http://staff.city.ac.uk/~ross/papers/FingerTree.pdf

is there a better way?

No, Seriously…

@chouser's implementation

ajp drops wisdom

double-list, counted-double-list, sorted-set are pretty usable

data.finger-trees

but rolling your own…

naive IIQM 1

— Alan Jay Perlis—

https://github.com/clojure/data.finger-tree

  • sorted array
  • find insertion point
  • insert O(n)
  • re-sum O(n)

we want a sorted tree

O(n)

naive IIQM 2

  • sorted
  • O(log n) lookup, insert
  • sorted array
  • find insertion point
  • insert O(n)
  • avoid re-sum

faster but still O(n)

Learn more about creating dynamic, engaging presentations with Prezi