Roberto Zunino:
> Yes, you are right, I didn't want to involve type classes and assumed
> 3::Int. A better example would be:
>
> polyf :: Int -> a -> Int
> polyf x y = if x==0 then 0
> else if x==1 then polyf (x-1) (\z->z)
> else polyf (x-2) ()
>
> Here, passing both ()
Can somebody explain to me exactly what the halting problem says? As I
understand it, it doesn't say "you can't tell if this program halts", it
says "you cannot write an algorithm which can tell whether *every*
program halts or not". (Similar to the way that Galios dude didn't say
"you can't sol
Matthew Brecknell wrote:
> Roberto Zunino:
>
>>Here passing both 3 and (\z->z) as y confuses the type inference.
>
> So the type inference is not really confused at all. It just gives a
> not-very-useful type.
Yes, you are right, I didn't want to involve type classes and assumed
3::Int. A bette
Christopher L Conway wrote:
On 5/14/07, Roberto Zunino <[EMAIL PROTECTED]> wrote:
Also, using only rank-1:
polyf :: Int -> a -> Int
polyf x y = if x==0 then 0
else if x==1 then polyf (x-1) (\z->z)
else polyf (x-2) 3
Here passing both 3 and (\z->z) as y confuses the
Roberto Zunino:
> Here passing both 3 and (\z->z) as y confuses the type inference.
Christopher L Conway:
> polyf :: forall a t1 t.
> (Num (t1 -> t1), Num a, Num t) =>
> a -> (t1 -> t1) -> t
>
> The inference assigns y the type (t1 -> t1) even though it is assigned
> the value 3?
Almost. It assi
Christopher L Conway wrote:
The inference assigns y the type (t1 -> t1) even though it is assigned
the value 3?
Yes, because type classes are open, and maybe you will demonstrate some
way to make t1->t1 an instance of Num.
Note the Num (t1 -> t1) constraint in the type...
On 5/14/07, Roberto Zunino <[EMAIL PROTECTED]> wrote:
Also, using only rank-1:
polyf :: Int -> a -> Int
polyf x y = if x==0 then 0
else if x==1 then polyf (x-1) (\z->z)
else polyf (x-2) 3
Here passing both 3 and (\z->z) as y confuses the type inference.
Actually, I t
Andrew Coppin wrote:
Right. So what you're saying is that for most program properties, you
can partition the set of all possible problems into the set for which X
is true, the set for which X is false, and a final set for programs
where we can't actually determine the truth of X. Is that about
Andrew,
Right. So what you're saying is that for most program properties,
you can partition the set of all possible problems into the set for
which X is true, the set for which X is false, and a final set for
programs where we can't actually determine the truth of X. Is that
about right?
Stefan Holdermans wrote:
This is rather typical in the field of program analysis. Getting the
analysis precise is impossible and reduces to solving the halting
problem. So, the next best thing is to get an approximate answer. An
import design guideline to such an analysis is "to err on the safe
Andrew,
Jules wrote:
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 b
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 fun
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
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) =
On Fri, 2007-05-11 at 12:10 +0100, Andrew Coppin wrote:
> Suppose I have you the source code to some arbitrary function that takes
> a list and returns another list.
>
> It is possible to determine whether the function always examins the
> entire input list?
Presumably you mean in the case that
Suppose I have you the source code to some arbitrary function that takes
a list and returns another list.
It is possible to determine whether the function always examins the
entire input list? Or would that be equivilent to solving the Halting
Problem? (Last time I checked, the Halting Problem
16 matches
Mail list logo
