Immutable data structures

[odipar]

Everything immutable! That's been my motto for almost a decade!

It seems that I'm not the only one: more and more frameworks share this 'immutability' property, including IPFS.

When I look at all the reddit and hackernews comments related to IPFS, most commenters are worried that IPFS cannot deal with 'dynamic' content. Nonsense!

But then you need to know that new (versions of) immutable data structures can be efficiently created, merged and altered, just like their mutable counterparts.

You just have to look at Clojure's Vector implementation to get an idea of how efficient immutable data structures can be in practice. In fact, there is a whole body of research out there that deal with various immutable data structures, such as:

• AVL Trees
• Ideal Hash Trees
• (B)Treaps
• (B)Skip-lists
• … and some of my own stuff…

Now the point is: all these data structures can be trivially Merkle-ized. Indeed, Merkle-zation is the premise of IPFS!

Of course, IPFS is much more. It needs strong P2P and DHT technology to make it a reality. But IPFS is also less, because it doesn’t provide a standard API to build (immutable) data.

For now, I’ll end with some related technology:

• Git(hub)/Fossil - immutable code / tickets
• Datomic - immutable database
• Condensation (https://condensation.io). Very similar to IPFS.
• Enchilada (http://www.enchiladacode.nl). Everything immutable, including computations.

So, do you think IPFS needs an API to build data structures? Or should that be left to the client, using IPFS?

[Kubuxu]

Please take a look at recently written specs for InterPlanetary Linked Data. It is standardised way with which applications can use to create data that can be directly stored in IPFS. https://github.com/ipfs/specs/blob/master/merkledag/ipld.md

I plan to work on Conflict-free Replicated Data Types on top of IPLD.

[odipar]

Yeah, I've read the specification, but it doesn't specify an API to manage/create/merge immutable data. So for example, an API like this (in scala):

def create(s: Array[Byte]): IPFS_DATA  // O(array.size)
def create(s: Array[IPFS_DATA]): IPFS_DATA  // O(array.size)
def concatenate(d1: IPFS_DATA, d2: IPFS_DATA): IPFS_DATA // O(log(n)) - n = total size
def splitAt(d: IPFS_DATA,  l: Location): (IPFS_DATA,IPFS_DATA) // O(log(n))
def destructure(d: IPFS_DATA): Array[IPFS_DATA] // O(array.size)

I believe that most Conflict-free Replicated Data Types also needs to be build on top of such immutable data structure API.