In a previous post, I wrote some information on ways to work with sorted infinite lists. Since then I have investigated some more and realise that the code I gave could be considerably improved. Particularly if you are interested in sorted finite lists.
The improvement
I made the remark that while
elem n primes
would not return for the infinite list primes, the alternative
(head $ dropWhile (<n) primes) == n
would work.
This is true, but it raises a couple of issues that need to be addressed before it can be used more widely.
The first problem is that it actually doesn’t work for finite lists, which is rather annoying but can be resolved by adding an appropriate test before taking the head:
contains n ns = (not $ null rest) && (head rest == n) where rest = dropWhile (<n) ns
The other issue with finite lists is that this is actually pretty inefficient and a better way to test for membership is to use sets. A much faster approach is this:
contains n ns = Set.member n $ Set.fromList ns
Even though this would appear to be doing a lot more work, it does appear to be considerably faster. However, this does not work for infinite lists, because the call to Set.fromList never terminates.
I have been making increased use of both of these methods to test for membership as I continue to work through Project Euler probems. Now at level 2!
Related posts:
- The fast, the right and the smart Working my
- Finding a member of an infinite list Haskell, a
{ 4 comments… read them below or add one }
Set.fromList is O(n log n) and has to traverse the whole list, while elem is O(n) and traverses only half of the list on average, there’s a clear winner here for me.
*But* Set.member is O(log n), so if you construct the Set only once and use it multiple times, then that’s a win. But then you should at least write
and hope that GHC does a nice optimizing job.
@Felipe
I took the liberty of editing your comment to use your most recent code snippet.
That all makes sense. One thing I struggle to understand is how much of a computation is kept around after it is evaluated once. From what you write, does the “let” force the evaluation and keep the result around? Or does that depend on the optimisation performed by the compiler?
I still have a lot to learn.
Thanks for the edit =). I’d like to have a preview button here.
I can’t get you a definite answer, but I think that GHC will share the Set on every optimization options, from -O0 to -O3, when using the definition I gave. However I don’t think it will share the Set on the post’s definition because that may create a space leak and the compiler can’t tell that the optimization is benign only by looking at the code.
Interesting. I guess as I write more Haskell, these things will become second nature – roll on that day…
I have added a plugin to allow the preview of comments – hope it works ok!