also try replacing that (foldl' intersect') with (foldr (flip intersect'))! OK, next question: Given that I'm using all the results from intersect', why is the lazy version better than the strict one? Is ghc managing to do some loop fusion?
haskell tends to prefer foldr where mls prefer foldl, be it for lazyness and short-circuiting operators, or because a tail-recursive function with a lazy accumulator is only an efficient way to construct inefficient expressions. so, the very first thing i tend to look for when someone ports a program from ml to haskell are tail recursions with non-strict accumulators. even using foldl', when constructing pairs in the accumulator, there's no guarantee that the pair components will be evaluated early even if the pairs themselves are forced. so replacing foldl with foldr when porting from ml to haskell tends to be a useful habit, unless there are good reasons for foldl. however, things seem to be a little bit more involved in this example: intersect' forces the first component, and ignores the second, never building nasty delayed combinations of old accumulator and list head in the new accumulator. but if you compare the outputs of -ddump-simpl, or if you export all definitions from main and compare the outputs of --show-iface, you'll find differences related to the the result of intersect': whether or not that result can be passed unboxed. Constructed Product Result Analysis for Haskell (2000) http://citeseer.ist.psu.edu/baker-finch00constructed.html i don't know the details, but in the foldr case, the result of intersect' seems to be passed unboxed, in the foldl' case, it isn't. i'll leave it to the experts to explain whether that has to be the case or whether it is an omission in the optimizer. claus
using a recent ghc head instead of ghc-6.6.1 also seems to make a drastic difference
$ uname -a CYGWIN_NT-5.1 cr3-lt 1.5.19(0.150/4/2) 2006-01-20 13:28 i686 Cygwin $ ghc --version The Glorious Glasgow Haskell Compilation System, version 6.6.1 $ gcc --version gcc.exe (GCC) 3.4.2 (mingw-special) Copyright (C) 2004 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ ghc --make Ray1.hs [1 of 1] Compiling Main ( Ray1.hs, Ray1.o ) Linking Ray1.exe ... $ time ./Ray1.exe >out real 0m55.705s user 0m0.015s sys 0m0.031s $ /cygdrive/c/fptools/ghc/ghc-6.7.20070613/bin/ghc --make Ray1.hs -o Ray1head.exe [1 of 1] Compiling Main ( Ray1.hs, Ray1.o ) Linking Ray1head.exe ... $ time ./Ray1head.exe >out.head real 0m24.989s user 0m0.031s sys 0m0.015s $ diff -q --binary out out.head $