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 ∀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? Nearly every example in every tutorial on types I can find has this unexplained phenomenon, or I'm really not reading carefully. |
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. |
Free forum by Nabble | Edit this page |