help with types and composition

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

help with types and composition

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>)

a -> a -> Bool could therefore mean either: "a function whose domain is an
'a' and whose codomain is a function from a to bool"; or "a function which
takes a function from type 'a' to 'a' and returns 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."

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. But, (a,
a) is not equivalent to (a -> a), and (a -> Bool) just doesn't make sense as
a range. It should be something like:

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

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

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?

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

Reply | Threaded
Open this post in threaded view
|

help with types and composition

Daniel Fischer-4
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.