Reimplementing “git clone” in Haskell from the bottom up (2013) | Hacker News Reader

Reimplementing “git clone” in Haskell from the bottom up (2013)

stefan.saasen.me

288 pointspoppingtonic39 comments

As somebody who has only recently started looking into functional programming, this was absolutely fascinating.

Even though I'm not very familiar with Haskell, I find this code much more concise and easy to follow compared to the original git-clone implementation in C. Though perhaps that's more down to the author's coding style?

As to your question, I think it is both. The author's ability to walk you through his thought processes in a clear and concise manner, his general strength as a writer, the fact that he added diagrams and models to help the reader, and that this did not seem to be written only for Haskellers to read... well they all add up to what you are describe. Kudos to the author.

I'm having an interesting experience with this at my job ... Haskell appears to be MUCH more approachable when you understand the problem at hand.

So much Haskell pedagogy wants you to write a compiler or a parser or ... whereas this article is taking you through a solution. And whaddyaknow -- Haskell comes across as gorgeous, elegant, compact, and highly comprehensible.

When I show a FIX server or REST API written in Haskell to a non-Haskeller coworker (ie everyone else :) ), with minimal explanation they're getting what's going on. I look forward to many more "Haskell-in-anger" articles to show the world how fantastic it is to work with.

Yes. Haskellers are just too much in love with compilers and parsers. Those are much easier to write in Haskell, but not enough people have grappled, and suffered (and failed) to write one in eg C to appreciate.

Author here. Thanks for the kind comment, happy to see that other people and not just myself got something out of this exercise.

In my experience, pure functional programming, combined with Haskell's relatively permissive syntax, allows for very natural-language-like and well-structured programs.

Languages like Agda can do this even more impressively. You can do stuff like write

    if_then_else_ : Bool -> a -> a -> a

And you can split up the "if", "then", and "else" and put the arguments where the underscores are.

Meh. I think it is arguable that the code from this article is as easy as it is to understand as much from the prose that goes with it as from the language it is written in. My argument would actually lean towards more so.

> I think it is arguable that the code from this article is as easy as it is to understand as much from the prose that goes with it as from the language it is written in.

This was hard to understand.

Apologies. I think I should have just written that in multiple sentences. I don't think mere commas can save it.

Simply put, my assertion is that it is the accompanying prose and diagrams that truly make the code easy to understand. Not its implementation language.

I would love to say that my terrible sentence above illustrates that prose is not a panacea. Well, I think I can claim that. I can not claim it was intentional. :)

For what it's worth, I found your original statement perfectly clear.

> Simply put, my assertion is that it is the accompanying prose and diagrams that truly make the code easy to understand. Not its implementation language.

Haskell does help somewhat, in that it's offers you a lot of flexibility in how to structure your program. So you can tailor your program to your explanation. (Knuth's literate programming tools help bring those capabilities and more to more conventional languages.)

The mixfix notation in Agda seems really amazing. I am always wishing I could write code like "add _ to _" or "sort _ by _", etc...

It's almost exactly smalltalk (circa 1980 or so) notation.

Agda mixfix supports things like:

    [ foo ]
    bar !
    ! baz

etc.

It also supports precedence parsing.

I don't Smalltalk can do all of these.

Smalltalk, unlike Agda, can probably omit the spacing around operators, though, while Agda can't :)

I probably should look more closely at Agda.

But the if_then_else_ example is basically smalltalk equivalant - although I suspect Agda will be able to do without the angle brackets that Smalltalk often needs in these cases.

Maude also allows mixfix like Agda.

There's an interesting example in the manual ( http://maude.cs.uiuc.edu/maude1/manual/maude-manual-html/mau... ) where juxtaposition is defined as an operation, specifically:

    op __ : Bits Bits -> Bits [assoc] .

The underscores are placeholders for arguments, just like in Agda, but there's no name defined! Since `0` and `1` are defined as constructors of `Bit` (which is a sub-type of `Bits`) this will parse values like `0101010` as `Bits`.

Haskell has sortBy and comparing, like this:

    sortBy (comparing salary) employees

The grammar is not as close to English, but close enough to understand.

The canonical example there is actually to use on and infix `` notation:

    sortBy (compare `on` salary) employeers

Shouldn't the then- and else-"branches" be made lazy?

They probably are already. (In Haskell, they would be by default. I don't know enough about Agda.)

That is indeed the case. In Agda, the default is call-by-name, which means that functions are applied before arguments are evaluated. This does not, however, include sharing, so evaluating

    (λ x → x + x) (fib 2000)

will evaluate `fib 2000` twice. Agda programs can also be compiled to Haskell, in which case they would have Haskell's evaluation strategy, which is generally call-by-need (and so would share the result of fib 2000 above.)

I've never been aware of whether Agda is CBN or CBV because it actually doesn't matter (!).

In a pure, terminating language like Agda evaluation is "confluent" which means that CBV and CBN evaluations are identical.

Identical up to one algorithm taking a few seconds, and another taking as long as the universe has been alive :)

Who runs Agda code anyway? :)

Not only CBV and CBN, but also strict evaluation.

Huh, for some reason I assumed that we were talking about Idris. I didn't read the post well enough.

Interesting. So "if foo then" would be a valid partial application?

Interesting.

It would also be a nice exercise to implement all of the internet RFCs, such as an email server, etcetera in Haskell. That's still a bit lacking. And it would be very useful if it existed, IMHO.

implementing a spec using haskell is a great learning exercise.

Implementing a spec is the only way you can use Haskell sensibly. All other uses are PITA.

I wrote an NFS server in Haskell, using Literal Haskell to implement all related RFC's 'inside' the RFC documents, interleaving code (lots of serdes stuff...) with the specification.

link please

Closed source (for now) I'm afraid...

Don't suppose anyone knows where those nice diagrams are from? (Hoping they're generated from a tool)

You're correct that they're generated from a tool, and it's diagrammix [1].

[1] http://www.reddit.com/r/programming/comments/1cgi2x/reimplem...

OSX :-(

It seems like the graphic shading could be replicated with SVG filter effects inserted as a post-processing stage applied to images output from Dia or Visio.

I quite like gliffy for styled diagrams. Not quite the same effect as the ones in the article, but still very nice. http://www.gliffy.com/

Ditaa is quite nice http://ditaa.sourceforge.net

It uses ASCII-art boxes, lines, etc. as input (which you can draw using Emacs's artist-mode, for example)

Reply on news.ycombinator.com