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/ <===
