[Haskell-cafe] Limits of deduction

[Rodrigo Queiro]

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 <andrewcoppin at btinternet.com> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070511/b4d84920/attachment-0001.htm