Yes, there was some discussion about this a few months ago.
It is still waiting for me to take a pass through the H98 report.
GHC's partition currently follows the (erroneous) Report implementation
rather than the specification.
Keep harassing me, so that I get down to the Report.
Simon
| -----Original Message-----
| From: Johannes Waldmann [mailto:[EMAIL PROTECTED]]
| Sent: 20 September 2000 07:54
| To: [EMAIL PROTECTED]
| Subject: List.partition is too strict
|
|
| The List.partition function has the specification
|
| partition :: (a -> Bool) -> [a] -> ([a],[a])
| partition p xs == (filter p xs, filter (not . p) xs)
|
| (see the Haskell98 report) but its implementation (also there)
|
| partition p xs = foldr select ([],[]) xs
| where select x (ts,fs) | p x
| = (x:ts,fs)
| |
| otherwise = (ts, x:fs)
|
| is too strict, as seen by evaluating
|
| let (a,b)= partition odd [1::Int ..] in print (take 3 a,take 3 b)
|
| which should give ([1,3,5],[2,4,6]). Both ghc-4.08 and
| hugs98-Feb-2000
| (PS: methinks the hugs version numbering scheme is ugly ugly ugly :)
| report stack overflow. However nhc98-1.0pre19 gets it right:
| because it has a "~" right before the (ts,fs) binding.
|
|
| Still, this is not a nice state of affairs.
|
| How can we reason formally about whether we need a pattern to be lazy,
| or about "black holes"? In Hudak's SOE book, it's in section 14.4,
| in an "experimental" fashion. Perhaps this approach is best suited
| for teaching: it exemplifies the problem, and shows a solution;
|
| but I'd like to have some formal tools
| that a) warn me that the problem could occur
| or rather b) prove that the "solution" really prevents it.
| Are there extensions of the type system that would be helpful?
|
| Best regards,
| --
| -- Johannes Waldmann ----
http://www.informatik.uni-leipzig.de/~joe/ --
-- [EMAIL PROTECTED] -- phone/fax (+49) 341 9732 204/252 --
===> Drittes Leipziger Jongliertreffen 6. - 8. Oktober <===
===> http://www.informatik.uni-leipzig.de/~joe/juggling/dreilei/ <===
