How to prepare a talk about Purely Functional Data Structures?

Community
1

The question seems to be easy but I have a serious constraint: the audience knows nothing about FP and I should not explain it

And now I’m in doubt because it seems that 3-hour talk is damned to be very sketchy. Current alorithmics packages in LaTeX seems to be too imperative by design to use…

The current plan is:

  • Present a syntactic unification and two approches to solve it: idempotent substitution using mutation and purely functional triangular one
  • How sharing works, why concatenation consing a list doesn’t copy entire list
  • Red-black trees, speculating that balancing in FP style will be shorter
  • Queues as two linked list, introduction to amortization
  • Numerical representations (?)
  • …
  • HAMT (?)

Any piece of advice?

2

My advice: use lots of images. The friendlier, the better. And watch this excellent talk for inspiration: https://youtu.be/Wo0qiGPSV-s

1 Like
3

Your title reminds me the Okasaki’s book. The first chapters present differents structures (in SML style but this doesn’t matter) and explain the memory representation for them. The book is a bit old in itself, but still a good scholar reference

4

Yeah, I’m planning to use it as a basis. AFAIK the only important thing that is not there is HAMT

5

what does the audience know? Can you use analogies from their domain? Accountants e.g. have a profound understanding of immutable ledger entries.

6

2nd year undergraduates. They probably know about linked lists and arrays. Maybe someone heard about RBTrees and more advanced stuff

7

I see, so it’s a mixed crowd concerning their every-day experiences. Hm. To me the memory efficiency of a linked list and re-usability of tails was an enlightenment. And that was embarrassingly late.

And “immutability changes everything”, https://doi.org/10.1145/2857274.2884038