I think it might be impossible. For the function: sumFirst n = sum . take n
then for any finite list, we can choose an n large enough that it will examine the whole list, even though the function is able to stop. This means the only way to check is to call it with an infinite list and see if it terminates, which might be impossible. However, maybe it is possible if this is a special case of the halting problem? On 11/05/07, Andrew Coppin <[EMAIL PROTECTED]> wrote:
>> 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
