[Haskell-cafe] Why doesn't GHC use the Hugs definition of
splitAt to avoid traversing the first part of the list twice?
Duncan Coutts
duncan.coutts at worc.ox.ac.uk
Sat Apr 26 05:51:46 EDT 2008
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
More information about the Haskell-Cafe
mailing list