I threw this example out:
every member of a data structure is traversed in a fold ("no early exits")
D. Tweed wrote:
I'm being terribly unfair here; this was probably just a simple slip when writing a hurried e-mail but if you mean what I think you mean about the fold:
undefd = undefd
f y x|y=='a' = "finished" |otherwise = y:x
g xs = foldr f "" xs
Main> g ('a':undefd) "finished"
shows that folds can exit early; if it didn't it'd black hole forever.
Hmm, is that a counterexample? That list has one member, 'a', which is indeed traversed... But that's a consequence of the linearity of lists. If you defined a fold over trees and then tried to evaluate n: data Tree a = Fork (Tree a) (Tree a) | Leaf a fold fork leaf (Fork t t') = fork (fold fork leaf t) (fold fork leaf t') fold fork leaf (Leaf a) = leaf a n = fold max id (Fork undefined (Leaf 5)) you would indeed miss a member. --- Frank Atanassow, Information & Computing Sciences, Utrecht University Padualaan 14, PO Box 80.089, 3508TB Utrecht, The Netherlands Tel +31 (0)30 253-3261 Fax +31 (0)30 251-3791