CODEWITHSUNDEEP
haskelltypes
Madderote
Madderote

Reputation: 1137

Haskell: function to find out by type definition

Also owing to all your help, I made some steps in understanding the type system in Haskell. What I still don't understand is a construction like this:

chk :: Eq b => (a -> b) -> a -> b -> Bool

Upvotes: 0

Views: 118

Answers (3)

n. m. could be an AI
n. m. could be an AI

Reputation: 120079

Ler's see how we could deduce a sensible implementation of chk from its type.

Having two values, one of type a and one of type b, we can't do much with them. Both types are unknown. (They may be in fact the same type but we don't know that). We know we can compare two values of type b for equality, but there's only one such value at our disposal. We can compare it with itself but this doesn't make much sense. If we had another value of type b, we could compare the two.

But there are three arguments, one of type a, one of type b, and one is a function of type a->b. The only other thing we can do with them (apart from comparing a value with itself) is to apply the function to the value of type a. The result of this application has type b. But wait, this is exactly what we wanted, another value of type b to complete the comparison. And since the result of the comparison is of type Bool, this is exactly what we need to complete chk.

chk f x y = f x == y

And this is the one of two non-trivial ways to write this function. The other one replaces == with /=.

There are in fact a very limited amount of functions of this type and we can enumerate them all. If you only take into account total functions and require that equality is reflexive and symmetric, then there are only two other functions of this type:

chk0 f x y = True
chk1 f x y = False

If you drop these restrictions, you can write also:

chk2 f x y = undefined
chk3 f x y = y == y // may be different from just True
chk4 f x y = f x == f x

and perhaps a dozen more.

Upvotes: -1

MathematicalOrchid
MathematicalOrchid

Reputation: 62848

You need to clearly separate in your mind the difference between type variables and normal variables.

The type (Eq b) =>... means that b can be any type, provided that values of that type are comparable. So b = Int would work, because we can compare Int values (e.g., 3 == 5 is false, but 2 == 2 is true). But b = IO Int would not work, since you cannot compare I/O operations for equality.

All of this has nothing to do with whether a == b; both a and b are types, not values. The type says that a can be any type, and b can also be any type (if it implements Eq). In particular, it's possible for a and b to be the same type, but it's also possible for them to be different types. Using different type variables says that these can be different types, not that they must be different.

Upvotes: 0

tomferon
tomferon

Reputation: 5001

Such a function would only be able to compare two values of type b for equality, no as involved.

If you look at the type, there is one implementation that seems to be the obvious one:

chk :: Eq b => (a -> b) -> a -> b -> Bool 
chk f x y =
  let z = f x -- z :: b
  in y == z -- comparison of two values of type b

Upvotes: 3

Related Questions