newbie conceptual question [from haskell list]
Thu, 26 Jul 2001 14:04:58 +0200
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
> undefd = undefd
> f y x|y=='a' = "finished"
> |otherwise = y:x
> g xs = foldr f "" xs
> Main> g ('a':undefd)
> 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