[Haskell-cafe] Limits of deduction

[Andrew Coppin]

>> 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.