Re: [Haskell-cafe] Composition Operator
On Tue, Sep 25, 2007 at 12:08:34AM -0500, Derek Elkins wrote: () is terminal, not initial. There exists a unique function to it (ignoring bottoms) from anything, namely, const (). A point of A categorically, is just a function from the terminal object to A, () - A. For the notion of pointed that you want, the important thing is that f = g :: A - B iff for all k :: () - A, f . k = g . k. I.e. a function is completely determined by its action on points. Ah, a lightbulb clicked with this one. Since functions are objects in this category, and we can't talk about function application 'cause that'd be breaking the object-bubble, we establish equivalency between function application and composition of a function with a point. Presumably, a proof is in order. (Sorry, feel free to ignore. Just a newb trying to catch up and convince himself he's not totally whacked.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composition Operator
Now you've triggered an addict attack. Remember how Haskell is a gateway drug? Composition (.) may not be an abstract function, but it is very fundamental one (so be wary of redefining the (.) operator in Haskell!). Only the identity function id is more fundamental. [And actually, these are polymorphic functions that each name an entire class of functions, one for each type of their arguments.] Together these obey the following very important laws: id . f = f f . id= f f . g . h = (f . g) . h = f . (g . h) If every Haskell type is an object, and each (strict) function is an arrow that maps its domain (the type before the first top-level - in the type signature) to its codomain (everything after that first top-level - in the type signature), and from the above laws we see that function composition (.) is associative, then these objects and arrows form a category Hask* [1]. Anyway, the above says that how the composition operator transforms *types*. The following says how the composed function transforms *values*: For any x of the appropriate type, id$ x = x f . g $ x = f (g x) Where did this definition of function composition come from (besides matching our intuition)? Not all categories are pointed, but our Haskell one is. This is the link between point-free (stuff before the $) and pointed (including the $ x) notation: if you know how each function acts on each value of its respective domain, then you know how the composite function acts on values in its domain. What is a point? A point in Hask* is a type with only a single value in it, from which all other values can be constructed. Every value x maps trivially into a function (const x), and when you apply this function to the (only) value of a point, you get x back. There is a built-in Haskell type () whose only value [besides undefined] is also called (), so we might as well take the type () as our point: id . const x $ () = const x $ () (f . g) . const x $ () = f . (g . const x) $ () = f . g . const x $ () But these laws come directly from the definition of a category (identity + associativity), so we see for a pointed category like Hask, composition has to be defined the way it is to be worthy of the name! The above formulation with $ () is the true pointed notation, but since flip const () = id, we can trivially apply the (const x) to our point () and get back x, so both left and right below are said to be in pointed notation: f . const x $ () = f $ x = f x Since x is a free variable (any definition of f and g can't guess what x will be chosen), we can drop the x as well, resulting in point-free notation: forall x . f x = g x == f = g. This defines equality of functions, but there is no generally computable way of deciding, given f and g, whether they are equal, without applying them both to every possible value of the domain. Anyway, I think the question you were originally asking is, how do you interpret the type signature of (.), or more generally what is the domain and codomain of a Haskell function. The algorithm is easy: count over to the first arrow (-) that is not inside any parentheses. Everything to the left is the domain, everything to the right is the codomain: (.) :: (b - c) - (a - b) - (a - c) domain | codomain (f .) = (.) f :: (a - b) - (a - c) f . g = (.) f = ((.) f) g :: (a - c) Each application of a function to its first argument (whose type is the domain) results in a value in the codomain. You can't go wrong if you stick to the interpretation that every function takes at most one argument (it may of course take no arguments!) Then you just partially apply each (leftmost) argument to peel off the domain, until you are left with no more arguments. I hope all of the above gave off more light than heat. There is a lot more to say about function composition, e.g. it is a monoid operation when applied to functions in a single type (a - a). But this e-mail's long enough, and you've probably already stopped reading :) , so I'll stop here as well. Dan Weston [1] I used the asterisk in the category name Hask* to exclude undefined values or partial functions PR Stanley wrote: Ah, I understand now. Let me get this right: The resulting (a - c) is a kind of abstract function formed by the pairing of a - b) and (b - c), hence the lambda \x - g (f x), correct? Thanks, Paul At 05:11 22/09/2007, you wrote: Hello, It's probably easiest to think of composition as a function which takes two arguments (both functions), (g :: b - c) and (f :: a - b), and returns a new function of type a - c. We could write this explicitly as composition :: (b - c, a - b) - a - c composition (g,f) = \x - g (f x) then (.) is the currying of composition: (.) = curry composition or (.) g f = \x - g (f x) -Jeff On 9/21/07, PR Stanley [EMAIL PROTECTED] wrote: Hi (.)
Re: [Haskell-cafe] Composition Operator
Of course I should have proofread this one more time! What is a point? A point in Hask* is a type with only a single value in it, from which all other values can be constructed. Every value x maps trivially into a function (const x), and when you apply this function to the (only) value of a point, you get x back. There is a built-in Haskell type () whose only value [besides undefined] is also called (), so we might as well take the type () as our point: Actually, a point is any one object, for Hask* it is any one monotype (e.g. (), [Int], (Char,Double)). The magic of an *initial* object (i.e. a type with only one nullary constructor such as () that has only one (defined) value) is that there is a *unique* function mapping it to any other type. But that's being greedy, since we don't need a unique function, just any one function. A forgetful function like const doesn't care which type its second argument is. Sorry for the muddle. Dan Weston Dan Weston wrote: Now you've triggered an addict attack. Remember how Haskell is a gateway drug? Composition (.) may not be an abstract function, but it is very fundamental one (so be wary of redefining the (.) operator in Haskell!). Only the identity function id is more fundamental. [And actually, these are polymorphic functions that each name an entire class of functions, one for each type of their arguments.] Together these obey the following very important laws: id . f = f f . id= f f . g . h = (f . g) . h = f . (g . h) If every Haskell type is an object, and each (strict) function is an arrow that maps its domain (the type before the first top-level - in the type signature) to its codomain (everything after that first top-level - in the type signature), and from the above laws we see that function composition (.) is associative, then these objects and arrows form a category Hask* [1]. Anyway, the above says that how the composition operator transforms *types*. The following says how the composed function transforms *values*: For any x of the appropriate type, id$ x = x f . g $ x = f (g x) Where did this definition of function composition come from (besides matching our intuition)? Not all categories are pointed, but our Haskell one is. This is the link between point-free (stuff before the $) and pointed (including the $ x) notation: if you know how each function acts on each value of its respective domain, then you know how the composite function acts on values in its domain. What is a point? A point in Hask* is a type with only a single value in it, from which all other values can be constructed. Every value x maps trivially into a function (const x), and when you apply this function to the (only) value of a point, you get x back. There is a built-in Haskell type () whose only value [besides undefined] is also called (), so we might as well take the type () as our point: id . const x $ () = const x $ () (f . g) . const x $ () = f . (g . const x) $ () = f . g . const x $ () But these laws come directly from the definition of a category (identity + associativity), so we see for a pointed category like Hask, composition has to be defined the way it is to be worthy of the name! The above formulation with $ () is the true pointed notation, but since flip const () = id, we can trivially apply the (const x) to our point () and get back x, so both left and right below are said to be in pointed notation: f . const x $ () = f $ x = f x Since x is a free variable (any definition of f and g can't guess what x will be chosen), we can drop the x as well, resulting in point-free notation: forall x . f x = g x == f = g. This defines equality of functions, but there is no generally computable way of deciding, given f and g, whether they are equal, without applying them both to every possible value of the domain. Anyway, I think the question you were originally asking is, how do you interpret the type signature of (.), or more generally what is the domain and codomain of a Haskell function. The algorithm is easy: count over to the first arrow (-) that is not inside any parentheses. Everything to the left is the domain, everything to the right is the codomain: (.) :: (b - c) - (a - b) - (a - c) domain | codomain (f .) = (.) f :: (a - b) - (a - c) f . g = (.) f = ((.) f) g :: (a - c) Each application of a function to its first argument (whose type is the domain) results in a value in the codomain. You can't go wrong if you stick to the interpretation that every function takes at most one argument (it may of course take no arguments!) Then you just partially apply each (leftmost) argument to peel off the domain, until you are left with no more arguments. I hope all of the above gave off more light than heat. There is a lot more to say about function composition, e.g. it is a monoid operation when
Re: [Haskell-cafe] Composition Operator
On Mon, Sep 24, 2007 at 06:47:05PM -0700, Dan Weston wrote: Of course I should have proofread this one more time! What is a point? A point in Hask* is a type with only a single value in it, from which all other values can be constructed. Every value x maps trivially into a function (const x), and when you apply this function to the (only) value of a point, you get x back. There is a built-in Haskell type () whose only value [besides undefined] is also called (), so we might as well take the type () as our point: Actually, a point is any one object, for Hask* it is any one monotype (e.g. (), [Int], (Char,Double)). The magic of an *initial* object (i.e. a type with only one nullary constructor such as () that has only one (defined) value) is that there is a *unique* function mapping it to any other type. But that's being greedy, since we don't need a unique function, just any one function. A forgetful function like const doesn't care which type its second argument is. () isn't an initial object. There are no initial objects in Hask-with-⊥, since every object admits at least four arrows to Bool (const True, const False, const undefined, and undefined). Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composition Operator
Well, I did footnote in my first e-mail that: [1] I used the asterisk in the category name Hask* to exclude undefined values or partial functions [Although I think I may have flipped the asterisk convention.] I see what you mean by const False and const True being two different arrows, but now I don't know how that reconciles with the Wikipedia Example 3 of http://en.wikipedia.org/wiki/Initial_object In the category of pointed sets (whose objects are non-empty sets together with a distinguished element; a morphism from (A,a) to (B,b) being a function f : A ? B with f(a) = b), every singleton is a zero object [i.e. both initial and final]. I thought I was being safe by distinguishing () as my distinguished element. Where did I go wrong? Dan Weston Stefan O'Rear wrote: On Mon, Sep 24, 2007 at 06:47:05PM -0700, Dan Weston wrote: Of course I should have proofread this one more time! What is a point? A point in Hask* is a type with only a single value in it, from which all other values can be constructed. Every value x maps trivially into a function (const x), and when you apply this function to the (only) value of a point, you get x back. There is a built-in Haskell type () whose only value [besides undefined] is also called (), so we might as well take the type () as our point: Actually, a point is any one object, for Hask* it is any one monotype (e.g. (), [Int], (Char,Double)). The magic of an *initial* object (i.e. a type with only one nullary constructor such as () that has only one (defined) value) is that there is a *unique* function mapping it to any other type. But that's being greedy, since we don't need a unique function, just any one function. A forgetful function like const doesn't care which type its second argument is. () isn't an initial object. There are no initial objects in Hask-with-?, since every object admits at least four arrows to Bool (const True, const False, const undefined, and undefined). Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composition Operator
Oh, duh! The only systematically distinguishable value in every type is undefined, but I went and excluded that value from my fake Hask* class. Never mind, I'll stop while I'm behind! :( Dan Weston wrote: Well, I did footnote in my first e-mail that: [1] I used the asterisk in the category name Hask* to exclude undefined values or partial functions [Although I think I may have flipped the asterisk convention.] I see what you mean by const False and const True being two different arrows, but now I don't know how that reconciles with the Wikipedia Example 3 of http://en.wikipedia.org/wiki/Initial_object In the category of pointed sets (whose objects are non-empty sets together with a distinguished element; a morphism from (A,a) to (B,b) being a function f : A ? B with f(a) = b), every singleton is a zero object [i.e. both initial and final]. I thought I was being safe by distinguishing () as my distinguished element. Where did I go wrong? Dan Weston Stefan O'Rear wrote: On Mon, Sep 24, 2007 at 06:47:05PM -0700, Dan Weston wrote: Of course I should have proofread this one more time! What is a point? A point in Hask* is a type with only a single value in it, from which all other values can be constructed. Every value x maps trivially into a function (const x), and when you apply this function to the (only) value of a point, you get x back. There is a built-in Haskell type () whose only value [besides undefined] is also called (), so we might as well take the type () as our point: Actually, a point is any one object, for Hask* it is any one monotype (e.g. (), [Int], (Char,Double)). The magic of an *initial* object (i.e. a type with only one nullary constructor such as () that has only one (defined) value) is that there is a *unique* function mapping it to any other type. But that's being greedy, since we don't need a unique function, just any one function. A forgetful function like const doesn't care which type its second argument is. () isn't an initial object. There are no initial objects in Hask-with-?, since every object admits at least four arrows to Bool (const True, const False, const undefined, and undefined). Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composition Operator
On Mon, 2007-09-24 at 19:11 -0700, Dan Weston wrote: Well, I did footnote in my first e-mail that: [1] I used the asterisk in the category name Hask* to exclude undefined values or partial functions [Although I think I may have flipped the asterisk convention.] I see what you mean by const False and const True being two different arrows, but now I don't know how that reconciles with the Wikipedia Example 3 of http://en.wikipedia.org/wiki/Initial_object In the category of pointed sets (whose objects are non-empty sets together with a distinguished element; a morphism from (A,a) to (B,b) being a function f : A ? B with f(a) = b), every singleton is a zero object [i.e. both initial and final]. I thought I was being safe by distinguishing () as my distinguished element. Where did I go wrong? () is terminal, not initial. There exists a unique function to it (ignoring bottoms) from anything, namely, const (). A point of A categorically, is just a function from the terminal object to A, () - A. For the notion of pointed that you want, the important thing is that f = g :: A - B iff for all k :: () - A, f . k = g . k. I.e. a function is completely determined by its action on points. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composition Operator
Tony Morris wrote: is the same as: (.) :: (b - c) - ((a - b) - (a - c)) .. accepts a function a to c and returns a function. The function returned takes a function a to b and returns a function a to c IMO, that should be accepts a function b to c and returns a function. The function returned takes a function a to b and returns function a to c Personally I also find the following a good explanation, since it does not introduce lambdas or other scary things for newbies. f . g = composite where composite x = f (g x) for example printLn = putStrLn . show so printLn x becomes putStrLn (show x) Cheers, Peter -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Apply parentheses from the right. So: (.) :: (b - c) - (a - b) - a - c is the same as: (.) :: (b - c) - (a - b) - (a - c) is the same as: (.) :: (b - c) - ((a - b) - (a - c)) How you read that is up to you, but here is one way of reading it: accepts a function a to c and returns a function. The function returned takes a function a to b and returns a function a to c The expression f(g(x)) in C-style languages is similar to (f . g) x Tony Morris http://tmorris.net/ PR Stanley wrote: Hi (.) :: (b - c) - (a - b) - (a - c) While I understand the purpose and the semantics of the (.) operator I'm not sure about the above definition. Is the definition interpreted sequentially - (.) is a fun taht takes a fun of type (b - c) and returns another fun of type (a - b) etc? Any ideas? Thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFG9JzXmnpgrYe6r60RAjDrAJ0SvkZHtNsctWNYHjqxjp9lnpNvgACfS/2r 9jwUvD29/ZMMot8x3/nvyI8= =xSzA -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composition Operator
Peter Verswyvelen: Personally I also find the following a good explanation, since it does not introduce lambdas or other scary things for newbies. f . g = composite where composite x = f (g x) I suppose that the usual definition, which is (f . g) x = f (g x), is clear enough. No lambdas to be scared of here. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composition Operator
Ah, I understand now. Let me get this right: The resulting (a - c) is a kind of abstract function formed by the pairing of a - b) and (b - c), hence the lambda \x - g (f x), correct? Thanks, Paul At 05:11 22/09/2007, you wrote: Hello, It's probably easiest to think of composition as a function which takes two arguments (both functions), (g :: b - c) and (f :: a - b), and returns a new function of type a - c. We could write this explicitly as composition :: (b - c, a - b) - a - c composition (g,f) = \x - g (f x) then (.) is the currying of composition: (.) = curry composition or (.) g f = \x - g (f x) -Jeff On 9/21/07, PR Stanley [EMAIL PROTECTED] wrote: Hi (.) :: (b - c) - (a - b) - (a - c) While I understand the purpose and the semantics of the (.) operator I'm not sure about the above definition. Is the definition interpreted sequentially - (.) is a fun taht takes a fun of type (b - c) and returns another fun of type (a - b) etc? Any ideas? Thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composition Operator
I'm not sure what you mean by abstract function. It's a function like any other function. But otherwise you're right. :) -- Lennart On 9/22/07, PR Stanley [EMAIL PROTECTED] wrote: Ah, I understand now. Let me get this right: The resulting (a - c) is a kind of abstract function formed by the pairing of a - b) and (b - c), hence the lambda \x - g (f x), correct? Thanks, Paul At 05:11 22/09/2007, you wrote: Hello, It's probably easiest to think of composition as a function which takes two arguments (both functions), (g :: b - c) and (f :: a - b), and returns a new function of type a - c. We could write this explicitly as composition :: (b - c, a - b) - a - c composition (g,f) = \x - g (f x) then (.) is the currying of composition: (.) = curry composition or (.) g f = \x - g (f x) -Jeff On 9/21/07, PR Stanley [EMAIL PROTECTED] wrote: Hi (.) :: (b - c) - (a - b) - (a - c) While I understand the purpose and the semantics of the (.) operator I'm not sure about the above definition. Is the definition interpreted sequentially - (.) is a fun taht takes a fun of type (b - c) and returns another fun of type (a - b) etc? Any ideas? Thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composition Operator
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Peter Verswyvelen wrote: Tony Morris wrote: is the same as: (.) :: (b - c) - ((a - b) - (a - c)) .. accepts a function a to c and returns a function. The function returned takes a function a to b and returns a function a to c IMO, that should be accepts a function b to c and returns a function. The function returned takes a function a to b and returns function a to c Oops! IMRevisedO too :) Tony Morris http://tmorris.net/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFG9Ym4mnpgrYe6r60RArGPAKCZHoJz2Sd6eSZs76xd+vqnCqJUBQCfeYzJ q1+WCoXqzRZVeIyeGPVhOC8= =12Iw -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Composition Operator
Hi (.) :: (b - c) - (a - b) - (a - c) While I understand the purpose and the semantics of the (.) operator I'm not sure about the above definition. Is the definition interpreted sequentially - (.) is a fun taht takes a fun of type (b - c) and returns another fun of type (a - b) etc? Any ideas? Thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composition Operator
Hello, It's probably easiest to think of composition as a function which takes two arguments (both functions), (g :: b - c) and (f :: a - b), and returns a new function of type a - c. We could write this explicitly as composition :: (b - c, a - b) - a - c composition (g,f) = \x - g (f x) then (.) is the currying of composition: (.) = curry composition or (.) g f = \x - g (f x) -Jeff On 9/21/07, PR Stanley [EMAIL PROTECTED] wrote: Hi (.) :: (b - c) - (a - b) - (a - c) While I understand the purpose and the semantics of the (.) operator I'm not sure about the above definition. Is the definition interpreted sequentially - (.) is a fun taht takes a fun of type (b - c) and returns another fun of type (a - b) etc? Any ideas? Thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Composition Operator
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Apply parentheses from the right. So: (.) :: (b - c) - (a - b) - a - c is the same as: (.) :: (b - c) - (a - b) - (a - c) is the same as: (.) :: (b - c) - ((a - b) - (a - c)) How you read that is up to you, but here is one way of reading it: accepts a function a to c and returns a function. The function returned takes a function a to b and returns a function a to c The expression f(g(x)) in C-style languages is similar to (f . g) x Tony Morris http://tmorris.net/ PR Stanley wrote: Hi (.) :: (b - c) - (a - b) - (a - c) While I understand the purpose and the semantics of the (.) operator I'm not sure about the above definition. Is the definition interpreted sequentially - (.) is a fun taht takes a fun of type (b - c) and returns another fun of type (a - b) etc? Any ideas? Thanks, Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFG9JzXmnpgrYe6r60RAjDrAJ0SvkZHtNsctWNYHjqxjp9lnpNvgACfS/2r 9jwUvD29/ZMMot8x3/nvyI8= =xSzA -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
