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

Fast Nearest Neighbor Queries in Haskell

izbicki.me

Post reply on HN
Print view View original

11–20 of 20 posts

Re: Fast Nearest Neighbor Queries in Haskell

#11

Post by codygman »

platz wrote: post #10
codygman wrote: post #8

Earlier quoted context omitted.

I've heard quite the opposite. I've heard that GHC is state of the art in the depth and breadth of optimizations it can perform. I'm struggling to remember if the context was "of everything" or just within pure functional programming.

GHC has great optimizations within the scope of modules (and seems to balance for the right level of polymorphism/modularity/linking), and can inline some things across module boundaries. But at the level of entire programs more advanced optimizations are possible; I gather there are tradeoffs too. http://mlton.org/ https://www.reddit.com/r/haskell/comments/2tpmbo/what_on_ear... http://stackoverflow.com/questions/472…

ML isn't that popular though right? Would it be fair to say GHC had the most impressive optimizations of mainstream language?

With that said I certainly wonder why ML isn't more popular!

Re: Fast Nearest Neighbor Queries in Haskell

#13

Post by amelius »

This algorithm operates on trees. But I've always wondered how one can create efficient algorithms operating on general graphs in a functional language such as Haskell?

For example, how would one write a fast version of Dijkstra's shortest path algorithm in Haskell?

Re: Fast Nearest Neighbor Queries in Haskell

#14

Post by dottedmag »

amelius wrote: post #13

This algorithm operates on trees. But I've always wondered how one can create efficient algorithms operating on general graphs in a functional language such as Haskell? For example, how would one write a fast version of Dijkstra's shortest path algorithm in Haskell?

E.g. using a variation of zippers

Re: Fast Nearest Neighbor Queries in Haskell

#16

Post by carterschonwald »

codygman wrote: post #7
sink wrote: post #4

Earlier quoted context omitted.

Great point. His concluding statement aligns with your observation: "So then why did I use Haskell? To make cover trees 10 times easier for programmers to use." Default Haskell is certainly not geared toward numeric performance even though it certainly can be with the right libraries.

You might be interested in this if you are interested in high performance numerical Haskell: https://github.com/wellposed/numerical Carter claims he can perform optimizations that aren't possible in other languages, though I can't personally speak to them since I'm not well versed in numerical code.

It's not yet in shape for general use, nor for being advocated. There is some tech there that's unique in terms of handing matrix computation on rich formats nicely.

I'd prefer if we reserve advocacy for when i get it to the point where there's public documentation, or at least examples :)

Re: Fast Nearest Neighbor Queries in Haskell

#17

Post by tel »

amelius wrote: post #13

This algorithm operates on trees. But I've always wondered how one can create efficient algorithms operating on general graphs in a functional language such as Haskell? For example, how would one write a fast version of Dijkstra's shortest path algorithm in Haskell?

Using mutability.

It's not a sin, just something to avoid when not strictly necessary.

http://jspha.com/posts/mutable_algorithms_in_immutable_langu...

http://jspha.com/posts/mutable_algorithms_in_immutable_langu...

http://jspha.com/posts/mutable_algorithms_in_immutable_langu...

Re: Fast Nearest Neighbor Queries in Haskell

#18

Post by tdees40 »

ximeng wrote: post #9

Some great posts on that site. https://izbicki.me/blog/turning-an-ak-47-into-a-serving-ladl... is good from the non Haskell perspective.

Mike's one of the more fascinating people around. One of the only people ever to receive a discharge from the navy as a conscientious objector after he became a pacifist.

Re: Fast Nearest Neighbor Queries in Haskell

#19

Post by codygman »

carterschonwald wrote: post #16
codygman wrote: post #7

Earlier quoted context omitted.

You might be interested in this if you are interested in high performance numerical Haskell: https://github.com/wellposed/numerical Carter claims he can perform optimizations that aren't possible in other languages, though I can't personally speak to them since I'm not well versed in numerical code.

It's not yet in shape for general use, nor for being advocated. There is some tech there that's unique in terms of handing matrix computation on rich formats nicely. I'd prefer if we reserve advocacy for when i get it to the point where there's public documentation, or at least examples :)

> I'd prefer if we reserve advocacy for when i get it to the point where there's public documentation, or at least examples :)

Very sorry, I'll keep quiet about it until you announce it is ready! :)

Re: Fast Nearest Neighbor Queries in Haskell

#20

Post by carterschonwald »

codygman wrote: post #19
carterschonwald wrote: post #16

Earlier quoted context omitted.

It's not yet in shape for general use, nor for being advocated. There is some tech there that's unique in terms of handing matrix computation on rich formats nicely. I'd prefer if we reserve advocacy for when i get it to the point where there's public documentation, or at least examples :)

> I'd prefer if we reserve advocacy for when i get it to the point where there's public documentation, or at least examples :) Very sorry, I'll keep quiet about it until you announce it is ready! :)

thanks, i hope that happens relatively soon, though i've been a bit buried with getting life in order, though thats finally moving along nicely.
Post reply on HN