[Haskell-cafe] Re: best strategy for comparing comparisons

[Michael Karcher]

Jason Dusek <jason.dusek at gmail.com> wrote:
[These are point 3 and 4]
>  .  Compare every Word32 with every other Word32 for equality,
>     and see how long it takes.
>  .  Ditto with ByteStrings.
> 
>   The first two are easy and I'm done with them already. The
>   latter two seem like they'll run afoul of laziness. I have two
>   ideas about how to do them:
> 
>  .  Do every comparison with a list comprehension, compressing
>     the result as I go using `all`.
all is not a good idea: It stops as soon as it sees one false.
Better count the number of equals.
  let count = length $ filter id [a==b,a <- bytestrings, b <- bytestrings]

>  .  Do every comparison in a recursive IO procedure.
Should work too. But you have to take care that implicit I/O thingies
don't spoil one version of your timing tests.

>   Are there other ways? Will strictness annotations, for
>   example, allow me to run comparisons on larger lists?
Strictness annotation might help, but I don't think they are the
correct tool to use here. The counting test I proposed above
should run in O(1) stack and heap, as well as O(n^2) time, which is
the best you can expect (of course, the list of bytestrings is O(n)
on the heap).

Regards,
  Michael Karcher