Hacker News Reader

JeanPierreon Understanding Clojure's Persistent Vectors, Pt. 3

Agreed on the benchmarks – that's the next (and last) part on the list I'm going to do with this series.

And yes, of course, at some point, constant factors break into applications. Would it be better if add in a short comment on "practically O(1) for non-HPC applications", or would you phrase it differently to give it better context?

JeanPierreon Understanding Clojure's Persistent Vectors, Pt. 3

I understand your concern, but I don't really think the problem is within Clojure people: When I started out explaining the structure to other people and that most operations have O(log n) runtime, people dismissed Clojure as being too slow for practical purposes. Part of this is because programmers, not Clojure devs in particular, connotate O(log n) with "much slower than O(1)". However, this data structure is incredibly much faster than the "O(log n)" people are generally used to.

And this is the problem. As you yourself say, most programmers usually associate/assume "Big-O notation is intended to describe how the time required for an operation grows as the number of items being handled gets large".

But formally, this is not the case at all. O(g(x)) tells you the that the worst case input to the algorithm will require less operations (usually operations, sometimes memory or other things) than the function g multiplied by some positive constant. g is usually determined by the size of the input. (This definition is also simplified somewhat, but it illustrates the problem)

We can say that ArrayLists.add have O(n) runtime and that quicksort have O(n²) runtime, but they both also have O(n³) and O(n!) runtime.

In addition, Big-O does not describe how the algorithm runs in the average case, or how frequent the worst case is. In and of itself, the Big-O notation tells us almost nothing about an algorithm – you barely conclude anything from it. I guess that is part of why it has become this very simplified term with a very wibbly-wobbly definition from time to time.

So when you're saying that calling it "practically O(1)" is lying, I agree if this was in an academic context. But for the average programmer (regardless of language!), O(g(x)) is usually thought of as the "worst case runtime for an algorithm". Since the actual runtime is – well – effectively constant, I considered it okay.

---

That being said, I have formally explained the persistent vector if you're interested in the academic version. The background chapter in http://hypirion.com/thesis.pdf should cover it.

JeanPierreon “Mostly functional” programming does not work

That's a red herring: You're asking why the majority of software is written in imperative languages instead of functional ones, which is a very complex question with very many factors. It is not an argument which invalidates nor counters the author's claim: Namely that "mostly functional languages" is unfeasible and only increases the bugs caused by side effects.

JeanPierreon Elm 0.12.1: Fast immutable arrays

Mori doesn't implement RRB-trees, thus doesn't support logarithmic concatenation.

JeanPierreon Elm 0.12.1: Fast immutable arrays

Constant time in practise is a notable difference from saying constant time.

I can always sort a 32-bit int array in worst case linear time using counting sort, which in theory is better than the worst case runtime of quicksort, O(n²). Is it better in practise? Of course not, the constant factor is just too high, both for time and memory.

JeanPierreon Trapperkeeper is a new Clojure framework for long-running applications, services

I've managed to do the opposite: Scala didn't stick, Clojure did. I guess there's some subjective reason why or why not Clojure/Scala would stick with someone.

However, it's false that Clojure doesn't have a company behind it: Cognitect is certainly backing up Clojure by developing ClojureScript and Clojure itself, Clojure consulting, the Datomic database and the Pedestal "framework".

JeanPierreon Where Lisp Fits

    And if you ask me, its just so good that we haven't needed a revision in 20 years.

What about threading and/or concurrency? CLTL doesn't mention it, yet it is something which is now considered a requirement for real, general purpose programming languages.

JeanPierreon Go by Example

Could you elaborate on how generics makes code less safe? In my experience, the lack of generics is much more type unsafe, as you often have to do casts at runtime (and handle them) when you have to implement your own data structures. In contrast, languages with generics handle those at compile time.

JeanPierreon Show HN: LINQ for Go

Just for reference, a single goroutine has a 8 kb stack size. Having one million of these things in memory at once would require 8 Gb of memory. Obviously, the scheduler kicks in, but 8 kb chunks of memory still has to be assigned and freed for every routine started and stopped.

JeanPierreon Clojure vs. Scala

Using val King = 13; val Queen = 12; in Scala is not equivalent with using Clojure keywords, as their printed variant will be 13 and 12, not :king and :queen. Reading debugging output or logs would force you to manually convert those values.

Ordering for free is valuable, I guess, but it sort of depends on the situation. Sometimes face cards are worth 10, other times they are worth 11, 12, 13. If you use val King = 10;, then it suddenly is impossible to distinguish between face cards and tens.

JeanPierreon Understanding Clojure's Persistent Vectors, Part 1

I do agree that the structure is influenced by the paper, so I've added that in. I don't agree that they are "virtually identical" however, because there are significant differences leading to a lot of performance improvements (never any hash collisions, insertion and removal only at the end, resulting in perfect balancing, etc) and, as swanodette mentioned, Bagwell himself mentioned that they were pioneered by Hickey.

> Rich goes through this in one of his talks but I don't recall which.

If you figure out which, I'd love to know! :)

JeanPierreon Understanding Clojure's Persistent Vectors, Part 1

Author here: I think you talk about the persistent hashmaps, not the persistent vectors. I've been looking for papers explaining Clojure's persistent collections, and Bagwell seems to cover the hash maps and hash sets quite well. However, I've not seen a paper on the persistent vectors, which was quite a bummer, and that was the reason I started explaining them in the first place.

If you have a reference to a paper explaining something similar (or the actual implementation), I'd love to put it in the post for others.

JeanPierreon Who Says C is Simple?

To get an even better explanation on what the word "simple" means and what it derives from, I would recommend "Simplicity Ain't Easy" by Stuart Halloway[1]. While it is very similar to "Simple made Easy", it focuses a lot more on the etymology of the words "simple" and "complex" and how people misuse the word.

[1]: http://www.youtube.com/watch?v=cidchWg74Y4

JeanPierreon LINQ Ruined My Favorite Interview Question

sort-by takes an optional comparator, so doing (comp - val) is a bit unneeded. Just add in > as an argument to sort-by:

  (->> (string/split s #"\s+")
       frequencies
       (sort-by val >)
       (take 10))

Just mentioning it here because I find it vastly more readable than (comp - val).

JeanPierreon Replacing Clever Code with Unremarkable Code in Go

I would like to add on to this:

Generics may not be the correct solution, but I would really like a way to make collections which are general enough to be used by any datatype. As of now, I cannot do that without doing the typical `interface{}` approach.

The built-in data structures + channels are able to handle this, but if I just want a set of elements, what do I do? Make a `map[foo] bool`? If I see such a piece of code in an unfamiliar code base, I have no idea whether to test for key existence or whether I have to test whether the bool is true. A generic set would leave me puzzled and type unsafe[1]: What types could possibly exist in this set? A set of foos is not that hard to comprehend, and is in fact very much more straightforward to understand than a generic set, which in unfamiliar code may contain anything, or a mapping from foos to bools.

[1]: Rob Pike mentions in http://www.youtube.com/watch?feature=player_detailpage&v... that type safety is of high importance for Golang, but how does one achieve that if all the different datatypes I implement/need use `interface {}` where I have to cast all values afterwards? That seems very type unsafe, from where I stand.

JeanPierreon Skycraft: Minecraft clone in WebGL

Well, there are some comments just about that in the "coming soon" part, and it seems that the selling point is about making multiplayer easier for you compared to Minecraft.

Whereas you have to host a Minecraft server yourself (or host a world on a LAN) in order to play multiplayer, Skycraft doesn't require you to do that. All you have to do is share a link with your friends. In addition, you can "[i]nvite anyone to fly or walk around in your world in spectator-mode", which I optimistically intepret as "walk around in my world without buying the game". (Of course, that's my take on it.)

JeanPierreon Iron Ring

Curiously, NTNU/NTH got a similar tradition which officially started in 1914, 8-11 years earlier[1, 2]. I wonder if these rings or the "identity crises" (the NTH-ring was designed to give former NTH (now engineering) students an identity, whereas this iron ring represents the obligations and ethics) have some correlation or not.

[1]: http://en.wikipedia.org/wiki/NTH_Ring

[2]: http://www.ntnu.no/ntnu/old/glos/glos_nr.5_1995/ringen.html

JeanPierreon Ruby is too slow for programming competitions

I partially disagree, partially agree.

In these competitions, it's about implementing a solution as fast as possible, while still get it working under the time limit (5/8 minutes). It's mostly about having the right idea and implement it.

In very many cases, you would like to be able to manipulate and play with algorithms and have efficient mutable data structures. For this, Java/C++ (Essentially C with data structures) is very suitable.

However, in some cases, you'd like to perform advanced simulations, mathematical calculations or manipulations where immutable data structures are more suitable. In those cases, you would LIKE to have magic: Arbitrary numbers, ratios, (efficient) immutable data structures and a more functional style would not only eliminate work, but also reduce the amount of errors you're likely to do.

The important part is that the implementation uses the right idea, not that the implementation is fast. Usually it's handy with a lower-level language to implement the algorithm right, but at times, a higher level (functional) language is better when it comes to implementation speed.

JeanPierreon Clojure 1.5

This is currently not possible with lein (bug/enhancement), but will be with 2.1.0. See #966[1] for details. As a workaround, any project dependent of Clojure 1.5.0 will utilize that for the repl. So when in a project using 1.5.0, the repl will be 1.5.0 too.

[1]: https://github.com/technomancy/leiningen/issues/966

JeanPierreon Clojure 1.5

There's a lot of new small improvements in this update which are great for Clojure users, but the fundamental difference between 1.4 and 1.5 is the reducer library which was implemented. It's added mostly for performance reasons: By using this library, you will utilize Fork/Join in Java, but with a functional interface instead of the "gory" one. Very interesting, because the complexity of a typical `(reduce (map ...))` won't change, and you're suddenly utilizing all the cores on your computer. Rich Hickey had a talk about the new Reducers library[1], and I'd recommend you to see it, as it gives you a good understanding of how it works (and why it was implemented that way).

Another slightly interesting thing is the sudden enhancement to read-eval and EDN[2]. That's mainly because of the rough weather Ruby/Rubygems was in with the YAML-exploits, which caused a heated discussion on how the Clojure reader should act by default[3][4].

[1]: http://www.infoq.com/presentations/Clojure-Reducers

[2]: https://github.com/clojure/clojure/blob/master/changes.md#21...

[3]: http://dev.clojure.org/jira/browse/CLJ-1153

[4]: https://groups.google.com/d/topic/clojure-dev/zG90eRnbbJQ/di...

JeanPierreon A Language Without Conditionals

I consider "n < 2" to be an expression evaluating to either true (1) or false (0). You can do basic if-else branching by considering true/false statements as conditions to if/elseif/else branching, but true/false cannot be used to evaluate only parts of a function by itself. That's what I intended to express, sorry if it's not evident.

JeanPierreon A Language Without Conditionals

Certainly, there's no practical difference between pointers+arrays, polymorphism and conditional statements. That's the whole point: We're "simulating" or "creating" if-statements/polymorphism using other language constructs.

My goal was to show that you can do conditional statements and polymorphism without having those constructs by implementing them on top of other constructs (and possibly vice versa). And by looking at them from a different angle, you may end up with some ideas which may or may not be of value, such as the debug-thing. Building a separate branch stack would be the same thing, the question at hand is how you find such an idea/solution to a problem.

JeanPierreon Leiningen version 2.0.0 released

Fast startup time can be achieved through Drip[1], which is rather easy to setup for Leiningen use.

[1]: https://github.com/flatland/drip/wiki/Clojure

JeanPierreon Swearjure - Clojure without alphanumerics

Should've been fixed now, thanks for mentioning.

JeanPierreon How Lisp is Going to Save the World

    If it is so good why ain't it is used more?

pg has written about this [1], and the main reason he found was that popularity is always self-perpetuating. If one of the languages get a head start with libraries, it's usually easier to develop programs and libraries within this language than other languages. If you know a popular language, you're more likely to have more job opportunities. If you're a manager, you would prefer to be able to replace programmers easily.

That's one of the reasons why Clojure started off on the JVM in the first place: It has libraries and an already thriving ecosystem. In addition, it's a nice bonus for language developers to not have to worry about performance related to GCing, threading, OS-specific differences etc, which the JVM abstracts away.

[1]: http://paulgraham.com/iflisp.html

JeanPierreon Xkcd style graphs

For people like me who would like to make PDF-reports with this kind of graph-style without resorting to Mathematica, take a look at this TeX-solution[1]. It utilizes the random step-decoration in Tikz to achieve a similar result.

[1]: http://tex.stackexchange.com/questions/74878/create-xkcd-sty...

JeanPierreon A sudoku solver in 33 lines of Clojure

People thinking "Oh god, not another x in y lines of z" (I first thought this as well), be open minded and try to read the code. It might not be in a language you know, but try and see if you can understand the last part:

  (run 1 [q]
    (== q vars)
    (everyo #(infd % (domain 1 2 3 4 5 6 7 8 9)) vars)
    (init vars hints)
    (everyo distinctfd rows)
    (everyo distinctfd cols)
    (everyo distinctfd sqs))

Which, for me, reads "Take one solution and return q, where q is equal to vars, and every var is either 1, 2, 3, 4, 5, 6, 7, 8 or 9. Then initialize the variables with the already placed elements we've been given, and ensure that every row, column and square has only distinct elements."

Now, I don't know about you, but this sounds actually like the rules of Sudoku for me, not some algorithm on how to solve it. That's amazing, and should really get you to think about trying out logic programming if you haven't already. There's a lot of power in it, and using it in production code might not be as far away as it seems.

JeanPierreon How the Norwegians Reacted to Terrorism

I think we're disagreeing on definitions and words, not what's going to change. We already have "high security" psychiatric wards, but they want to increase the security and have specific people placed in those "especially high security" wards. People can be placed there if there is a risk of "attacks against the patient themselves", which is as far I know not (directly) caused by mental disorder in the patient.

Take a look at http://www.regjeringen.no/nb/dep/hod/dok/regpubl/prop/2011-2... - esp. § 4A-8, which states the new changes in the law.

JeanPierreon How the Norwegians Reacted to Terrorism

The problem was that if the court declares Breivik insane, Norway couldn't (legally) put him in a high-security criminal prison.

That's wrong - they can do that without Lex Breivik. The issue is when he's declared healthy, what would then happen? It's legal to detain him if it can be proved that he constitutes a danger to society. However, if he is not considered a danger to the society, he will be able to walk freely. With Lex Breivik, they will be allowed to detain him as long the society is a danger to the person.

Think about that for a moment. With Lex Breivik, you can be isolated even if you've not done anything illegal (or have finished serving your imprisonment) or is considered healthy, because some people in the society want to do you harm.

JeanPierreon How the Norwegians Reacted to Terrorism

There have been no changes to the law to increase the powers of the police and security services, terrorism legislation remains the same and there have been no special provisions made for the trial of suspected terrorists.

A white lie, I'm afraid. Lex Breivik [1] has changed the laws so that regional security departments have a lot more power, in fact more power than what prisons have as of today.

[1]: http://www.google.com/translate?hl=en&ie=UTF8&sl=no&...