Am Montag 06 Juli 2009 13:53:01 schrieb Dan Douglas:

Hello everyone! first post here. I'm working through YAHT and Real World Haskell sort of in parallel. I have a somewhat related question.

Assume we have a binary operator which is not a higher order function. The "greater than" relation for example:

Prelude List> :t (>) (>) :: forall a. (Ord a) => a -> a -> Bool

Type classes and variables make sense - I assume since we have quantifiers, the type classes must be essentially predicates, and the type variables are bound to them as expected. Also I assume whenever we see (a -> b) this means roughly f:(<domain> -> <codomain>)

Correct.

a -> a -> Bool could therefore mean either: "a function whose domain is an 'a' and whose codomain is a function from a to bool";

Yes, that's it.

or "a function which takes a function from type 'a' to 'a' and returns a bool.

That would be the type (a -> a) -> Bool.

According to YAHT:

"NOTE The parentheses are not necessary; in function types, if you have a -> b -> y it is assume that b -> y is grouped. If you want the other way, with a -> b grouped, you need to put parentheses around them."

In short: (->) is right associative, a -> b -> c -> d === a -> (b -> (c -> d))

I'm confused by this. A function which takes multiple arguments should be equivalent to a predicate bound to some n-tuple. Or in this case of a binary infix operator, equivalent to a prefix operator which takes a tuple.

Correct.

But, (a, a) is not equivalent to (a -> a),

Indeed it isn't, the two sets don't even have the same cardinality (except a contains only one element). But (a -> a) -> Bool is *not* equivalent to a -> (a -> Bool).

and (a -> Bool) just doesn't make sense as a range.

But it does. (a -> Bool) is a perfectly reasonable set/Haskell type. Functions whose result is a function are very common in functional programming.

It should be something like:

(>) :: forall a. (Ord a) => (a, a) -> Bool

Note that, (ignoring _|_ and partial functions), the types ((a,b) -> c) and (a -> (b -> c)) are isomorphic. The isomorphism is given by curry :: ((a,b) -> c) -> (a -> (b -> c)) curry f = \x y -> f (x,y) and uncurry :: (a -> (b -> c)) -> ((a,b) -> c) uncurry g = \(x,y) -> g x y

Someone on freenode told me that if you had:

foo :: a -> b bar :: b -> c baz :: c -> d

and:

bork = (baz . bar . foo)

then:

bork :: a -> d

Yup.

Which, if correct means Haskell should always chain types for first-order functions. And since (>) is transitive, it should satisfy ∀x∀y∀z(((x,y) ∈ R & (y,z) ∈ R) -> (x,z) ∈ R) and omit the case for (y,z).

???

How it is possible to express a function which takes multiple arguments (or any first-order function at all) with more than one arrow/map symbol? How does this even make sense?

It gets even worse with more complicated examples:

Prelude List> :t foldl foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a

Prelude List> :t (>>=) (>>=)

:: forall (m :: * -> *) a b. (Monad m) => m a -> (a -> m b) -> m b

How do the non-existent associativity rules make complex function types seemingly without enough parentheses have unique meaning?

The associativity rules exist: (->) associates to the right. Hence, fully parenthesised: foldl :: (a -> (b -> a)) -> (a -> ([b] -> a)) Due to the right associativity, you can omit three pairs of parentheses.

Nearly every example in every tutorial on types I can find has this unexplained phenomenon, or I'm really not reading carefully.