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

Git is a purely functional data structure (2013)

blog.jayway.com

Post reply on HN
Print view View original

11–20 of 99 posts

Re: Git is a purely functional data structure (2013)

#11

Post by nine_k »

Edmond wrote: post #6

Perhaps for those familiar with "functional data structures" such an analogy is helpful but I find it easier to simply explain git for what it is without adding more exotic nomenclature to it. Git lets you do version control via full snapshots as opposed to just tracking diffs (even though it does actually do this too behind the scene). You can think of a full snapshot as saving a copy of your project structure every…

Exactly. Those familiar with functional data structures would thus point you at git and say: heres a structure from the Okasaki book that you use every day.

One more step is to point that futures / promises, and even lists, are monads that a e.g. JS programmer uses every day, too. It reminds me of the old literary character who did not know that he's been speaking prose all his life.

Re: Git is a purely functional data structure (2013)

#12

Post by mannykannot »

I think the author has a point in saying that learning Git by trying to map it to Subversion is not the best way to do it, but I don't think analyzing it as a functional data structure adds much insight. To me, it is easier to understand when you look at its purpose, and how it solves the problems of that domain - and the biggest difficulties of version control are on account of the problem being essentially one of distributed, lockless concurrency, something not mentioned in this article.

Re: Git is a purely functional data structure (2013)

#13

Post by _0w8t »

klodolph wrote: post #10
_0w8t wrote: post #3

Git is not a purely functional data structure [1] [1] man git-rebase

If Git were purely functional, you would expect rebase not to modify the existing data in any way, and indeed that is exactly what happens. You can create, delete, or modify only the top-level pointers: branch names, reflog, etc. Instead, rebase creates a completely new set of commits, and points the current branch at a new one. This is exactly how functional data structures work in e.g. Haskell, where "inserting" an…

Git rebase alters the structures that are relevant for me, like heads of named branches. In Haskell let bindings are immutable. To reference to the results one has to put them into new bindings. I.e. if Git was purely functional, the rebase would create new names for branches.

Re: Git is a purely functional data structure (2013)

#15

Post by davidcuddeback »

erikb wrote: post #9

A data structure cannot be functional. I understand what he's trying to say, and agree with most of it, but the word "functional" is purely wrong. What he wants to say is "good". But not all "functional programming" is good, nor is all good programming functional by necessity, despite what your local Lambda The Ultimate nerd tries to tell you. The Best, when it comes to data structures is a Directed, Acyclic Graph. F…

> A data structure cannot be functional.

I think the author is using the term "purely functional data structure" to mean a data structure that lends itself to an implementation in a purely functional language [1,2].

[1] https://en.wikipedia.org/wiki/Purely_functional_data_structu...

[2] https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...

Re: Git is a purely functional data structure (2013)

#16

Post by Simon_says »

19870213 wrote: post #5
_0w8t wrote: post #3

Git is not a purely functional data structure [1] [1] man git-rebase

But git-rebase does not alter existing commits in the commit tree, it simply creates a new branch (meaning new commits) on the tree.

Alright wiseguy, git gc.

Re: Git is a purely functional data structure (2013)

#17

Post by BenoitEssiambre »

I sometimes like to explain things the other way around. Immutability being version control for program state.

I rarely use functional programming but I certainly see its appeal for certain things.

I think the concept of immutability confuses people. It really clicked for me when I stopped thinking of it in terms of things not being able to change and started instead to think of it in terms of each version of things having different names, somewhat like commits in version control.

Functional programming makes explicit, not only which variables you are accessing, but which version of it.

It may seem like you are copying variables every time you want to modify them but really you are just giving different mutations, different names. This doesn't mean things are actually copied in memory. The compiler doesn't need to keep every versions. If it sees that you are not going to reference a particular mutation, it might just physically overwrite it with the next mutation. In the background "var a=i, var b=a+j", might compile as something like "var b = i; b+=j";

Re: Git is a purely functional data structure (2013)

#18

Post by randomsearch »

rubenbe wrote: post #4

I often recommend people to read "Git Internals". If you know how git works internally, it's much easier to understand how it works and the reasons behind it. https://git-scm.com/book/en/v1/Git-Internals

This suggests a poor abstraction.

Re: Git is a purely functional data structure (2013)

#19

Post by how_gauche »

erikb wrote: post #9

A data structure cannot be functional. I understand what he's trying to say, and agree with most of it, but the word "functional" is purely wrong. What he wants to say is "good". But not all "functional programming" is good, nor is all good programming functional by necessity, despite what your local Lambda The Ultimate nerd tries to tell you. The Best, when it comes to data structures is a Directed, Acyclic Graph. F…

> A data structure cannot be functional. I understand what he's trying to say, and agree with most of it, but the word "functional" is purely wrong. What he wants to say is "good". But not all "functional programming" is good, nor is all good programming functional by necessity, despite what your local Lambda The Ultimate nerd tries to tell you.

Why is it that whenever functional programming comes up, "real programmers" come out of the woodwork to bloviate, only to expose just how little they actually know about the topic?

"Purely functional" in this case is a jargon term that relates to Okasaki's 1996 PhD thesis, available online (https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf). It's a classification for data structures much in the way "regular" or "context-free" or "turing-complete" serve as classifications for grammars.

For a data structure to be "purely functional" (and no, article author does not mean "good" here) simply means that it's implementable in a pure functional language without mutation. Examples of non-functional data structures would be ones where mutation is intrinsic to how its algorithms work: traditional linear probing hash tables, union-find for graphs, etc.

By this technical criterion, the git object graph is clearly a purely functional data structure, sorry.

Re: Git is a purely functional data structure (2013)

#20

Post by davidcuddeback »

Simon_says wrote: post #16
19870213 wrote: post #5

Earlier quoted context omitted.

But git-rebase does not alter existing commits in the commit tree, it simply creates a new branch (meaning new commits) on the tree.

Alright wiseguy, git gc.

I don't understand what point you're trying to make. Unreachable data can be garbage-collected in Haskell, ML, Clojure, Erlang, and many other functional (and non-functional) programming languages. What about GC is supposed to refute that a data structure is functional?
Post reply on HN