3 ms·
As much as I find Haskell elegant for many things, I have to agree. It reminds me of the infamous Haskell "quicksort" which isn't actually quicksort because it'
by Tainnor 1y ago
As much as I find Haskell elegant for many things, I have to agree. It reminds me of the infamous Haskell "quicksort" which isn't actually quicksort because it's not in place.
I think not every piece of code needs to be hyper-optimised and in those cases, higher-level (declarative) languages where you don't specify every detail of the algorithm can give rise to very elegant code. But writing very performant Haskell code is a bit trickier.
In the anagram case, there's a straightforward O(n) solution where you count the occurrence of each letter in a hash map for both words and compare those. That can be written in Haskell too, of course, but it's not going to be as short.
- jose_zap 1y agoInterestingly, the naive solution presented in this article is O(n) thanks to laziness.
- deleted 1y ago[deleted]
- foldr 1y agoIt’s O(n log n). If the strings contain the same letters then you end up fully sorting both lists, and there’s no magical way of doing that in O(n) time with a general purpose sorting algorithm. The article is just saying that the best case performance improves because you don’t have to fully sort both lists in the case where the two words are not anagrams. There are other cases where laziness works its magic in relation to sorting, though. For example, “sort the list and then take the first element” is (with a suitable implementation of ‘sort’) an O(n) implementation of “find min/max element of list” in Haskell.