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

81–90 of 98 posts

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

#81

Post by dang »

Related. Others?

Purely Functional Data Structures in Elm – course lecture notes (2015) - https://news.ycombinator.com/item?id=12145741 - July 2016 (15 comments)

What's new in purely functional data structures since Okasaki? (2010) - https://news.ycombinator.com/item?id=11056704 - Feb 2016 (42 comments)

Purely Functional Data Structures (1996) [pdf] - https://news.ycombinator.com/item?id=10486481 - Nov 2015 (13 comments)

Okasaki: Purely Functional Data Structures (1996) [pdf] - https://news.ycombinator.com/item?id=8327838 - Sept 2014 (1 comment)

What's new in purely functional data structures since Okasaki? (2010) - https://news.ycombinator.com/item?id=7081191 - Jan 2014 (17 comments)

Ten Years of Purely Functional Data Structures (2008) - https://news.ycombinator.com/item?id=5701396 - May 2013 (24 comments)

What's new in purely functional data structures since Okasaki? - https://news.ycombinator.com/item?id=1983461 - Dec 2010 (2 comments)

What's new in purely functional data structures since Okasaki - https://news.ycombinator.com/item?id=1713594 - Sept 2010 (1 comment)

"Purely Functional Data Structures" by Chris Okasaki [pdf] - https://news.ycombinator.com/item?id=1138979 - Feb 2010 (12 comments)

Teaching, Playing, and Programming: Ten Years of Purely Functional Data Structures - https://news.ycombinator.com/item?id=112270 - Feb 2008 (2 comments)

Chris Okasaki's PhD thesis on purely functional data structures (pdf) - https://news.ycombinator.com/item?id=8221 - April 2007 (1 comment)

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

#82

Post by dang »

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-...

A few discussions:

What's new in purely functional data structures since Okasaki? (2010) - https://news.ycombinator.com/item?id=11056704 - Feb 2016 (42 comments)

What's new in purely functional data structures since Okasaki? (2010) - https://news.ycombinator.com/item?id=7081191 - Jan 2014 (17 comments)

What's new in purely functional data structures since Okasaki? - https://news.ycombinator.com/item?id=1983461 - Dec 2010 (2 comments)

What's new in purely functional data structures since Okasaki - https://news.ycombinator.com/item?id=1713594 - Sept 2010 (1 comment)

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

#83

Post by scott_s »

shepherdjerred wrote: post #49
fjeifisjf wrote: post #46

Earlier quoted context omitted.

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.

You're right, there are plenty of papers focusing on real-world performance. I chose not to capture the nuance because I wasn't sure how to express it succinctly.

How I see it: computer science as an academic field is roughly split between theory and systems. The theory folks tend to evaluate progress through proofs. The systems folks tend to evaluate progress through experiments.

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

#84

Post by bafe »

mefarza123 wrote: post #51
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 th…

I'm not so sure about cyby2, the persistence is based on "conventional" relational DBs. Judging by the paper, the main goal wasn't developing a specialised functional data structure to store molecules

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

#85

Post by odipar »

Okasaki got me interested in confluently persistent data-structures, way back in the 2000s.

They seem magical! To be able to combine data from the past with current data, efficiently!

They are almost always trees, with the exception of skip-lists, with all operations O(log(n)), .

After creating my own programming language Enchilada that is based on immutable data structures, I started considering what I deemed "next level":

Uniquely represented confluently persistent data structures

Combined with a Merkle tree encoding of such uniquely represented data structures (they are almost always trees), you can efficiently and incrementally authenticate them. Think 'block chain' on steroids, with incremental cryptographic hashes. Or torrents, if you are into that kind of thing.

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

#86

Post by 082349872349872 »

mklauber1 wrote: post #31

Definitely read that headline as "Purely Fictional Data Structures". My disappointment is immense.

Purely Fictional Data Structures include:

  To Queue a Mockingbird
  The Call-stack of the Wild
  Tesselation of the d'Urbervilles
  One Flew Over the Cuckoo Hash
  The Data of the Woosters
  Brideshead Re-visitor
  The Catcher in the Trie
  Les Miser-tables
  The Nat-elim of Monte Cristo

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

#87

Post by alex_lav »

I would love to be educated. I've seen claims about the merit and value of functional programming throughout my (nowadays relatively long) programming career. In practice I've never once seen those values or merits come to fruition - just the same cycle all software goes through.

My very direct experience recently has been Scala + cats resulted in the same buggy nonperformant software it was meant to prevent. I understand that bad programmers produce bad programs, regardless of language, but I feel pretty strongly that good tools prevent some amount of the typical "bad" that makes bad programs bad (ignoring the obviously maliciously bad examples). So I don't really understand, and would like to understand, if, how and when pure FP (and I suppose FP in general) actually improve quality of code/life outside of toy examples.

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

#89

Post by mrkeen »

alex_lav wrote: post #87

I would love to be educated. I've seen claims about the merit and value of functional programming throughout my (nowadays relatively long) programming career. In practice I've never once seen those values or merits come to fruition - just the same cycle all software goes through. My very direct experience recently has been Scala + cats resulted in the same buggy nonperformant software it was meant to prevent. I under…

The bottom line is that pure FP means that the same input to a function gives you the same output.

When you debug, you just give the program the same input which was problematic and you get to reproduce the error.

Persistent data structures make it less wildly inefficient to do so.

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

#90

Post by xmcqdpt2 »

amelius wrote: post #72
gnulinux wrote: post #48

Earlier quoted context omitted.

> 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...

"Computer science is no more about computers than astronomy is about telescopes." -- Edsger W. Dijkstra However, I do believe that astronomers put references to the actual instruments they used in their publications.

So do most algorithms papers that have benchmarks in them. It's not always useful though, because information about how this algorithm compares to some other one on a PDP-10 doesn't necessarily translate to modern machines.
Post reply on HN