Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Purely Functional Data Structures (1996) [pdf]

cs.cmu.edu

Post reply on HN
Print view View original

51–60 of 98 posts

Re: Purely Functional Data Structures (1996) [pdf]

#51

Post by mefarza123 »

gexahaha wrote: post #12

There's also a nice addendum on cstheory.stackexchange, "What's new in purely functional data structures since Okasaki?" - https://cstheory.stackexchange.com/questions/1539/whats-new-...

Since Okasaki's work there have been several advancements and new developments in the field:(Source: MirrorThink.ai)

1. PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections - 2022: This paper introduces PaC-trees, a purely functional data structure that supports parallel and compressed collections. PaC-trees are designed to be efficient in terms of space and time complexity while maintaining the benefits of functional data structures.

2. Proving tree algorithms for succinct data structures - 2019: This paper discusses the development of tree algorithms for succinct data structures, which are compact representations of data that support efficient query and update operations.

These is some work in other fields too:

1. CyBy2: a strongly typed, purely functional framework for chemical data management - 2019-12-30: This paper presents CyBy2, a purely functional framework for managing chemical data. The framework is designed to be strongly typed and enforce referential transparency through the type system.

2. chemf: A purely functional chemistry toolkit - 2012-12-20: This paper introduces chemf, a purely functional chemistry toolkit that provides a set of algorithms and data structures for working with chemical data in a functional programming context.

Re: Purely Functional Data Structures (1996) [pdf]

#52

Post by nerdponx »

gnulinux wrote: post #48
tmtvl wrote: post #39

It's weird that there are so many claims in here that the data structures and algorithms are perfectly performant yet there isn't even one look at generated assembly or any acknowledgement of the underlying system that is supposed to run the code. Proving things are Big O performant is neat, but at some point the code has to hit hardware.

> It's weird It's not weird, this is standard in academic computer science. It would be weird to do otherwise . In a theoretical dissertation/paper like this you can't just randomly bring up compiled assembly, it's completely and utterly off topic, it's not any more on topic than bringing up if the code was ran by an interpreter, or JVM, or transpiled to Haskell, or ran on GPU etc...

I can't speak for other fields, but in statistics and machine learning, it's not uncommon to see at least some practical experiments or simulations alongside theoretical results, or at least some discussion of practical considerations.

There are definitely plenty of pure theory papers as well, and pure theory is still a contribution. However one would at least hope to see subsequent work that does focus on the practical aspect.

Re: Purely Functional Data Structures (1996) [pdf]

#53

Post by taeric »

red_admiral wrote: post #33
1MachineElf wrote: post #26

What are software bugs that can be avoided by choosing data structures like these? I'm making a broad, high-level presentation about immutability in technology. At my company we have folks who have heard of it in the context of ransomware-resilient backups, others who have heard of it in the context of infrastructure as code, and very few who have heard of it in terms of data structures (distributed and non-distribut…

_Immutable_ data structures (not 100% the same thing, but a lot of overlap) avoid all kinds of concurrency problems, because you can safely pass them around and you'll never get a data race. You don't even need any locking (just to make things complicated, _lock-free_ data structures are another closely related but not identical concept). Once you're running a distributed system, this kind of stuff comes into its own…

Careful with this wording. They avoid shared memory mutations. They don't necessarily change data races. Rather, they just change them since, by definition, every edit is now creating stale data.

At large, in distributed software, this is a distraction. Since most passing of messages around from one distributed piece to the other was already doing a copy across mediums. Such that sent data was already immutable from the senders perspective. (Granted, the preparation step can have you step on your own feet.)

Re: Purely Functional Data Structures (1996) [pdf]

#54

Post by rgbgraph »

fjeifisjf wrote: post #46
shepherdjerred wrote: post #42

Earlier quoted context omitted.

> at some point the code has to hit hardware Yes, but that's not a concern of a computer scientist. Implementation and execution of the algorithm are up to the reader. It's like complaining that engineers don't do enough novel computer science research; of course they don't! It's not their job.

That's a very naive view of computer science. That is the attitude of people who have given up and decided that computers are too big for science now.

I’ve vouched for this, because it brings up an interesting point (albeit, one that proven provocative and been expressed before). Also, many of your comments are dead.

Big O/algorithmic complexity is interesting in that it tends to abstract away the architecture of the underlying processor. A copy is a copy is a copy. Arithmetic is arithmetic is arithmetic. Regardless of what instructions/processing units the underlying processor has. Regardless of data access. Regardless of parallelization. Regardless of memory complexity. All we use are brutish units of “work” — despite not all “workers” being equal.

It reminds me a bit of scientific management: treating your “workers” as interchangeable units that carry out what has been decided to be the most efficient movements and processes — completely disregarding the individual characteristics of the worker. For a humanist example, consider the individual quirks of the physiology (not only in size, length, and composition of the skeletal system via the muscles, bones, tendons and so on that would necessitate there being specific movements and workloads that best suit them — but also in psychology; the brain as its own work-producing part that is uniquely suited and most efficient for specific workloads; rather than an all-encompassing abstract average “best workstyle” that makes no note of these characteristics, but simply decides to use external metrics like “time to pick up a box using X, Y, or Z form.”)

The same parallel can be drawn to computers: different processors and collections of hardware (what is essentially the “body and brain”) have different quirks and different workloads they perform best at. For example, GPUs are much more useful in the case of vectorized/parallel workloads where the operations are relatively simple (f.e matrix arithmetic). While you can run an iterative matrix multiplication algorithm on a CPU in n^3 time — your data access costs will be significant. Instead, running a parallel algorithm on a GPU, with RAM very close by, you can achieve log^2 n.

This is where CS research really shines: not running away from the realities of physical systems, but embracing them.

Re: Purely Functional Data Structures (1996) [pdf]

#56

Post by toolslive »

EddieEngineers wrote: post #55

Why would we want to use purely functional data structures? When do the pros of functional data structures outweigh the additional complexity? Are there scenarios when a project would want to pivot from a regular data structure to a purely functional one?

they have some nice properties that you might want to benefit from. For example, they're persistent: every previous state of the data structure is still in there.. aka snapshots!

Re: Purely Functional Data Structures (1996) [pdf]

#57

Post by anfelor »

gexahaha wrote: post #12

There's also a nice addendum on cstheory.stackexchange, "What's new in purely functional data structures since Okasaki?" - https://cstheory.stackexchange.com/questions/1539/whats-new-...

I would also recommend Koen Claessen's simplified finger trees (https://dl.acm.org/doi/abs/10.1145/3406088.3409026) and Zip trees (https://arxiv.org/pdf/1806.06726.pdf) for purely functional skip lists.

Re: Purely Functional Data Structures (1996) [pdf]

#59

Post by Tainnor »

tmtvl wrote: post #39

It's weird that there are so many claims in here that the data structures and algorithms are perfectly performant yet there isn't even one look at generated assembly or any acknowledgement of the underlying system that is supposed to run the code. Proving things are Big O performant is neat, but at some point the code has to hit hardware.

Yeah, Big-O notation is only part of the picture and yes, "galactic algorithms" that are theoretically efficient but only for astronomically big inputs do exist, but in many cases (especially if your algorithm isn't doing anything particularly deep or clever) linear is faster than quadratic which is faster than exponential on real world input, too.

Mathematics is the science of modeling and abstraction and that abstraction exists in order to make the process of knowledge gathering easier. It works very well for the sciences, so I would say the method has been proven. Of course, if the models turn out to be completely inappropriate, that would be different, but so far, the simple machine models used (implicitly or explicitly) in the analysis of algorithms seem to be rather reasonable.

The alternative that you suggest, trying to benchmark concrete implementations of algorithms has so many confounders that it would be very hard to execute properly. I'm sure people are doing this too, but the formal Big O proof has a different quality to it because it does not depend on those particulars.

Re: Purely Functional Data Structures (1996) [pdf]

#60

Post by wtetzner »

smabie wrote: post #13
aeonik wrote: post #11

I'm reading this book right now. It's really great so far! I've been working a lot with Trees in Clojure, and have been hitting serious limitations of my understanding. I also found this YouTube video from a Clojure conference that reviews some different strategies for tree traversal in Clojure: https://youtu.be/YgvJqWiyMRY I thought that learning a Functional Lisp would make it really easy to traverse trees, since t…

I feel like they are.. not so awesome: they are grossly inefficient due to all the pointer chasing and are pretty much guaranteed to be slower than the alternative since they trash your cache.

They're only grossly inefficient if you wouldn't otherwise need to frequently make copies of large mutable data structures. It all depends on what you're trying to do.
Post reply on HN