[Haskell-cafe] Why doesn't GHC use the Hugs definition of splitAt to avoid traversing the first part of the list twice?

[Duncan Coutts]

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