Re: [Haskell-cafe] Limits of deduction

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