Definitely read that headline as "Purely Fictional Data Structures". My disappointment is immense.
Purely Functional Data Structures (1996) [pdf]
31–40 of 98 posts
Re: Purely Functional Data Structures (1996) [pdf]
#32What 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…
I think the point is that these data structures can be the foundation of a pure-functional style of programming.
You wouldn't drop these into an ecosystem where the programmers are used to dealing with mutable structures.
Now, whether using a purely functional language correlates with writing less bugs is a separate discussion, not sure what the modern consensus is.
Re: Purely Functional Data Structures (1996) [pdf]
#33What 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.
Re: Purely Functional Data Structures (1996) [pdf]
#34Earlier quoted context omitted.
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.
I wish I could remember the exact book, I think it's _writing solid code_. There was a long example about the excel evaluation engine back in the day when it was shipped on CD's and had to be perfect. The approach was, use one big dumb slow, but understandable and correct implementation, in parallel, use the lightning fast super whiz bang new implementation. Since both shared the same interface, they could be swapped…
I wanted to verify the book reference, and I think you could be correct.
There is a website for it: https://writingsolidcode.com/
The Amazon page it links to includes a few Index pages in the preview. I saw these under E:
Excel number formatting code 163
Excel's dialog handling code 113
Re: Purely Functional Data Structures (1996) [pdf]
#35What 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…
As the peer comment points out, functional data structures force you to be deliberate about where/when state changes take place. In particular, they force you to be cognizant of which version of a data structure a particular piece of code is referencing.
Immutable structures can help significantly in reducing race conditions in parallel code, as it is impossible for one thread to modify part of a data structure while another thread is accessing it. Each thread sees a consistent 'version' of the data structure until the code explicitly replaces it with a new version.
Immutability can also help with memory optimizations: A node of one data structure can be safely re-used in another data structure. For example, if you need to retain older versions of a tree, you can share common nodes (this is how GIT encodes version changes).
Re: Purely Functional Data Structures (1996) [pdf]
#36What 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…
Disclaimer: Not a programmer - I do not have a CS degree. One of my minors as an undergrad was MIS and while I took a database programming course as a senior, my knowledge is limited.
The high-level explanation I recall reading years ago somewhere (Joel on Software, I think??) was that a) Functional programs have no side effects, leading to the notion that b) They can, without much effort, be adapted for parallel tasks.
The example here was MapReduce, which was the original guts of the Google Search algorithm.
E.g, Things are fast because we can send your query to many, many computers to find an answer, and chances are good that that machine is (relatively) close to you, which means low wait times to get your answer.
Re: Purely Functional Data Structures (1996) [pdf]
#37What 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…
Purely functional data structures are a means, not an end in themselves.
Programming with immutable values and the more declarative style they support does design out at least one infamous source of bugs: shared mutable state. That has become increasingly important in recent years, for example because modern chips support ever increasing numbers of concurrent threads in hardware and because a lot of the software we write is now part of distributed systems.
That programming style has other advantages in terms of readability and reasoning about code. If you can be confident that a particular name in the code always refers to the same value once it’s been defined, tracing the flow of data through a function or through an entire system often becomes much easier. Having more understandable code naturally tends to improve reliability, among other advantages.
If we adopt that programming style then we still need to represent collections of values and different relationships within our data, but we can’t always use “traditional” data structures to do that any more because many of them rely on mutability, which we have excluded. So we need other ways to represent structured data that are compatible with immutability and declarative style, and that is what purely functional data structures give us.
Re: Purely Functional Data Structures (1996) [pdf]
#38Earlier quoted context omitted.
TypeScript is much less readable than Haskell and OCaml, but you can easily find translations to TypeScript such as https://github.com/skeate/lambdata .
> TypeScript is much less readable than Haskell and OCaml That's like saying that Norwegian is much less readable than Italian. It is in the eye of the beholder. They can both express the same concepts but which one is more readable depends on which one you already know.
Using this to push Brainfuck at work
Re: Purely Functional Data Structures (1996) [pdf]
#39It'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.
Re: Purely Functional Data Structures (1996) [pdf]
#40my dream language is rebol with immutable data structures only