[Haskell-cafe] Limits of deduction

[Jules Bean]

Andrew Coppin wrote:
>
> 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.
>


It's computationally impossible, in general. I can write something silly 
like

f (x:xs) = x : (UniversalTuringMachine(x) `seq` xs)

and it reduces to the halting problem.

However, it might be tractable for a large class of sensible programs. 
Someone around here might be aware of some relevant research?

Jules