It is possible to determine whether the function always examins the
entire input list?
Presumably you mean in the case that you examine the entire output list,
or do you mean when you only examine the output enough to see if it's a
[] or (:) (i.e. to WHNF) ?
f1 [] = []
f1 (x:xs) = if x < 0 then [x] else f1 xs
This function does not always examine the entire input list.
f2 [] = 0
f2 (x:xs) = x + f2 xs
This function *does* examine the entire list. Always.
There are many possible variations - length examines the whole list, but
not the elements *in* the list. null does less than that. And so on. I'm
sure there are many possible combinations. What I'm wondering is if it's
possible to algorithmically decide which class of functions an arbitrary
source fragment belongs to, or whether this is computationally impossible.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
