newbie conceptual question [from haskell list]

[Frank Atanassow]

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