On Fri, 2008-04-25 at 17:30 +0100, Richard Kelsall wrote:
I've just been investigating a performance oddity in using splitAt on a long stream of random numbers. I don't understand why GHC appears to want to traverse the first part of the list twice.
GHC seems to implement the splitAt function something like
splitAt n xs = (take n xs, drop n xs)
whereas Hugs is something like
splitAt n (x : xs) = (x : xs', xs'') where (xs', xs'') = splitAt (n-1) xs
which seems much more sensible to me. Wouldn't it be better to change GHC to the Hugs method? Have I misunderstood something?
Actually GHC uses this definition, in GHC.List: #ifdef USE_REPORT_PRELUDE splitAt n xs = (take n xs, drop n xs) #else /* hack away */ splitAt (I# n#) ls | n# <# 0# = ([], ls) | otherwise = splitAt# n# ls where splitAt# :: Int# -> [a] -> ([a], [a]) splitAt# 0# xs = ([], xs) splitAt# _ xs@[] = (xs, xs) splitAt# m# (x:xs) = (x:xs', xs'') where (xs', xs'') = splitAt# (m# -# 1#) xs #endif /* USE_REPORT_PRELUDE */ So ghc's version should be of equivalent strictness to the hugs version. What's interesting here is that the H98 specification of splitAt is silly. It got 'simplified' from a previous version of the Haskell spec and is so doing it was made less strict. With this definition: splitAt n xs = (take n xs, drop n xs) splitAt _|_ _|_ = (_|_, _|_) but with the sensible definition it'd return _|_ and that's really the only point of having splitAt, so that you can walk down the list once rather than twice. If someone needs the very lazy version there's always take and drop. Duncan