Can Your List Library Do This? | Hacker News Reader

Can Your List Library Do This?

dvanhorn.lambda-calcul.us

55 pointsswannodette12 comments

This article seems kind of poorly written. I guess it's some kind of sparse data structure written in a functional way -- the numerical linear algebra people have been doing similar things with sparse matrices and vectors for decades now. I wish there was more motivation and explanation here rather than most of the post being a monospace printout of digits.

Not to mention no units on the timings, and no explanation as to why the heck you'd want to calculate 2^100000. (Or is that just a convenient way to construct a very long list?) Glad I wasn't the only one puzzled by it.

Edited to add: Ah, based on other comments, it's constructing a list of 2^100000 of the same symbol, and then later on, 2^100000 - 1 of that symbol and 1 of another symbol. Which I guess is interesting, but doesn't seem wildly impressive?

the first time i read it, i thought he was computing 2^N and turning it into a list of digits. but, no, he was making a list of that length.

so, if you're going to pose a challenge to people, you should clearly describe what you're doing and why.

Especially because once we've sorted out what he is trying to demonstrate (I think) it seems dead trivial to duplicate? I mean, the only thing stopping me from doing that same demo with blazing speed in the deadly slow Rakudo Perl 6 compiler is the speed of calculating 2^100000....

PS For what it's worth, I'm guessing he's doing something more interesting than the dead simple implementation I'm imagining...

I'm going to show my ignorance and ask for a bit more of an explanation please?

Looks like random list generation using PLT scheme. The long number is the actual list, printed without breaks.

EDIT: apparently not, see below

Nope. The long number is the length of the list (i.e., the number of elements in the list.)

They built a list of 2 to the 100000th X's and then asked for its length. There's only a link for explanation of how, but I believe they represent a list as a DAG, so the repeated structure gets encoded compactly.

It builds a list of 2^100000 'x items (to put it in perspective a petabyte is 2^50) so obviously the list is not realized.

I've only just glanced at the source, but it seems to be based on the data structure explained on pg 77 of http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf.

Anybody know what the units are on the (time) calls? Makes a big difference whether these are seconds, ms, or μs.

It is milliseconds according to the Racket documentation.

http://docs.racket-lang.org/reference/time.html?q=time#(def....)

Reply on news.ycombinator.com