[Haskell-beginners] help with types and composition

[Daniel Fischer]

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
> &#8704;x&#8704;y&#8704;z(((x,y) &#8712; R & (y,z) &#8712; R) -> (x,z)
> &#8712; 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.