what are the points in pointsfree?
i'm not naive enough to think they are the composition function, and i've gathered it has something to do with free terms, but beyond that i'm not sure. unless it also has something to do with fix points?
On 12/14/06, Steve Downey
i'm not naive enough to think they are the composition function, and i've gathered it has something to do with free terms, but beyond that i'm not sure. unless it also has something to do with fix points?
The "points" are the arguments. The term comes from mathematics but I'm not sure where.
sdowney:
i'm not naive enough to think they are the composition function, and i've gathered it has something to do with free terms, but beyond that i'm not sure. unless it also has something to do with fix points?
The wiki knows all! :) http://haskell.org/haskellwiki/Pointfree 1 But pointfree has more points! A common misconception is that the 'points' of pointfree style are the (.) operator (function composition, as an ASCII symbol), which uses the same identifier as the decimal point. This is wrong. The term originated in topology, a branch of mathematics which works with spaces composed of points, and functions between those spaces. So a 'points-free' definition of a function is one which does not explicitly mention the points (values) of the space on which the function acts. In Haskell, our 'space' is some type, and 'points' are values. -- Don
the wiki wasn't half as clear. other tham covering the first half,
that it doesn't mean the '.' function.
so pointsfree is a step beyond leaving the domain unspecified.
my reading knowledge of haskell at this point far exceeds my ability
to write haskell. but so far, it has seemed to me that functions
written in the pf style are the most reuseable.
from what you just told me, it's not an artifact of the pf style, but
that maximally reusable functions will be expressible in a pointsfree
style. that those functions embody a pattern of computation, without
concern for the details.
On 12/14/06, Donald Bruce Stewart
sdowney:
i'm not naive enough to think they are the composition function, and i've gathered it has something to do with free terms, but beyond that i'm not sure. unless it also has something to do with fix points?
The wiki knows all! :)
http://haskell.org/haskellwiki/Pointfree
1 But pointfree has more points!
A common misconception is that the 'points' of pointfree style are the (.) operator (function composition, as an ASCII symbol), which uses the same identifier as the decimal point. This is wrong. The term originated in topology, a branch of mathematics which works with spaces composed of points, and functions between those spaces. So a 'points-free' definition of a function is one which does not explicitly mention the points (values) of the space on which the function acts. In Haskell, our 'space' is some type, and 'points' are values.
-- Don
G'day all.
Quoting Steve Downey
from what you just told me, it's not an artifact of the pf style, but that maximally reusable functions will be expressible in a pointsfree style.
Not necessarily. (There's a fairly obvious reductio ad absurdum argument as to why: at least the primitives like "map" and "foldr" need to be expressed in a pointed way!) Pointsfree functions are not necessarily maximally reusable, but they're usually maximally refactorable. As an example, the associative law for monads looks like this in pointed style: (m >>= k1) >>= k2 = m >>= (\x -> k1 x >>= k2) Applying this law from left to right requires introducing a fresh variable, which involves checking for name clashes, even if only briefly, and introduces a new name that doesn't necessarily have a good "meaning". Applying the law from right to left might require a lot of fiddling with k1 to get it in the right form, and checking that the variable, x, is not free in m or k2. In point-free style, the associative law for monads looks like this: join . join = join . fmap join In either direction, this is almost trivial. Cheers, Andrew Bromage
Donald Bruce Stewart wrote:
sdowney:
i'm not naive enough to think they are the composition function, and i've gathered it has something to do with free terms, but beyond that i'm not sure. unless it also has something to do with fix points?
The wiki knows all! :)
http://haskell.org/haskellwiki/Pointfree
1 But pointfree has more points!
A common misconception is that the 'points' of pointfree style are the (.) operator (function composition, as an ASCII symbol), which uses the same identifier as the decimal point. This is wrong. The term originated in topology, a branch of mathematics which works with spaces composed of points, and functions between those spaces. So a 'points-free' definition of a function is one which does not explicitly mention the points (values) of the space on which the function acts. In Haskell, our 'space' is some type, and 'points' are values.
Hm. I've been lurking for a while, and this might be a bit of nit-picking as my first post, especially given I'm still a bit of a n00b in Haskell. I've been programming a long time, though - coming up on three decades now and virtually all of it really programming, no management. Anyway, as I understood it, the "points" were the terminal objects of the category in which you're working - in this case, pointed continuous partial orders (CPO), and the points are effectively values in the domain. The usage of "point" for terminal objects comes from the category of topological spaces, as you say,. and algebraic topology is where category theory found it's first big home - but that's not really what we're talking about here, is it? Category theory got the term from topology, which got it from geometry. So you could say "point" is "position without dimension" - but that's just not the "point" we're talking about anymore. So, the usage of "point" here refers a terminal object in the CPO category, which means a value of some datatype - in this particular case, a value in the domain of the function being defined. So when you give a definition that uses patterns for the parameters, the variables in the patterns get bound to the values in the domain of the function. If you write the function in a higher-order style, where you don't bind the values, your definition doesn't refer to the "point" at which it's being evaluated, hence "point-free". -- ----- What part of "ph'nglui bglw'nafh Cthulhu R'lyeh wagn'nagl fhtagn" don't you understand?
No fair. Although I've a B.S. in Mathematics, I spent most of my time
in complex analytic dynamical systems, rather than hanging with the
algebraists. Except for a bit where I did some graph theory.
Rather ironic.
On 12/15/06, Scott Brickner
Donald Bruce Stewart wrote:
sdowney:
i'm not naive enough to think they are the composition function, and i've gathered it has something to do with free terms, but beyond that i'm not sure. unless it also has something to do with fix points?
The wiki knows all! :)
http://haskell.org/haskellwiki/Pointfree
1 But pointfree has more points!
A common misconception is that the 'points' of pointfree style are the (.) operator (function composition, as an ASCII symbol), which uses the same identifier as the decimal point. This is wrong. The term originated in topology, a branch of mathematics which works with spaces composed of points, and functions between those spaces. So a 'points-free' definition of a function is one which does not explicitly mention the points (values) of the space on which the function acts. In Haskell, our 'space' is some type, and 'points' are values.
Hm. I've been lurking for a while, and this might be a bit of nit-picking as my first post, especially given I'm still a bit of a n00b in Haskell. I've been programming a long time, though - coming up on three decades now and virtually all of it really programming, no management.
Anyway, as I understood it, the "points" were the terminal objects of the category in which you're working - in this case, pointed continuous partial orders (CPO), and the points are effectively values in the domain. The usage of "point" for terminal objects comes from the category of topological spaces, as you say,. and algebraic topology is where category theory found it's first big home - but that's not really what we're talking about here, is it?
Category theory got the term from topology, which got it from geometry. So you could say "point" is "position without dimension" - but that's just not the "point" we're talking about anymore.
So, the usage of "point" here refers a terminal object in the CPO category, which means a value of some datatype - in this particular case, a value in the domain of the function being defined. So when you give a definition that uses patterns for the parameters, the variables in the patterns get bound to the values in the domain of the function. If you write the function in a higher-order style, where you don't bind the values, your definition doesn't refer to the "point" at which it's being evaluated, hence "point-free".
-- ----- What part of "ph'nglui bglw'nafh Cthulhu R'lyeh wagn'nagl fhtagn" don't you understand?
Hello, Please view my claims with a healthy dose of scepticism: I know a little category theory, but only from the mathematical point of view, not as employed in computer science. Scott Brickner wrote:
Anyway, as I understood it, the "points" were the terminal objects of the category in which you're working - in this case, pointed continuous partial orders (CPO), and the points are effectively values in the domain.
Not quite. By a "point" /of X/ (X an object of your category) one usually means a morphism from the terminal object to X. The terminal object itself is essentially unique, and is the abstract version of "a space/set/type with only one point" (which you may call a point, if you like). I don't know what CPO is, but if it's anything like the category of Haskell types and functions, the terminal object is bound to be the type '()', having one value '()'. So in CPO, a "point" of X would be a function from '()' to X, corresponding to a particular value of type X (namely the value of the function at '()').
Category theory got the term from topology, which got it from geometry. So you could say "point" is "position without dimension" - but that's just not the "point" we're talking about anymore.
In the category of topological spaces, the terminal object is the one-point space, and the abstract point of X correspond directly to the usual points of X (its elements), just as in CPO. I would say that the concept of "point" is very similar.
So, the usage of "point" here refers a terminal object in the CPO category, which means a value of some datatype - in this particular case, a value in the domain of the function being defined. So when you give a definition that uses patterns for the parameters, the variables in the patterns get bound to the values in the domain of the function. If you write the function in a higher-order style, where you don't bind the values, your definition doesn't refer to the "point" at which it's being evaluated, hence "point-free".
Except for the "terminal object in the CPO category" part, I agree. Points are just values, and a point-free definition is one that does not mention specific points of its domain. Greetings, Arie
On 15/12/06, Scott Brickner
Donald Bruce Stewart wrote: sdowney:
i'm not naive enough to think they are the composition function, and i've gathered it has something to do with free terms, but beyond that i'm not sure. unless it also has something to do with fix points?
The wiki knows all! :)
http://haskell.org/haskellwiki/Pointfree
1 But pointfree has more points!
A common misconception is that the 'points' of pointfree style are the (.) operator (function composition, as an ASCII symbol), which uses the same identifier as the decimal point. This is wrong. The term originated in topology, a branch of mathematics which works with spaces composed of points, and functions between those spaces. So a 'points-free' definition of a function is one which does not explicitly mention the points (values) of the space on which the function acts. In Haskell, our 'space' is some type, and 'points' are values.
Hm. I've been lurking for a while, and this might be a bit of nit-picking as my first post, especially given I'm still a bit of a n00b in Haskell. I've been programming a long time, though - coming up on three decades now and virtually all of it really programming, no management.
Anyway, as I understood it, the "points" were the terminal objects of the category in which you're working - in this case, pointed continuous partial orders (CPO), and the points are effectively values in the domain. The usage of "point" for terminal objects comes from the category of topological spaces, as you say,. and algebraic topology is where category theory found it's first big home - but that's not really what we're talking about here, is it?
The point that the wiki article is trying to make is that the term "points-free" was first used in the context of algebraic topology, and generalised quickly from there. This may have even been before people were making the generalisation from elements of a set with a topology on it to maps from a terminal object to the space in question. It's a bit of a coincidence that the theory which we're using to describe the semantics of programs is topological in nature, the term would likely have found use here without that. - Cale
'Point free' is standard mathematical terminology for nothing more than the style of defining functions without making direct reference to the elements the functions act on. This style is exemplified by category theory and the reason it's called 'point free' rather than 'element free' is that category theory arose from algebraic topology where many of the functions under discussion act on sets of points in a topological space. 'Point' certainly doesn't refer to anything to do with CPOs and relating this use of the word point to arrows from terminal objects doesn't work too well if you consider vector spaces where maps from terminal objects don't correspond to (the usual notion of) points. -- Dan (Apologies if you received this message twice.)
Here, I think an examples worth a thousand poi....err, words. This one
comes from YAHT. Consider the two implementations of the following
function:
lcaseLetters :: String -> String
lcaseLetters s = map toLower (filter isAlpha s)
lcaseLetters :: Strint -> String
lcaseLetters = map toLower . filter isAlpha
Both functions will do the exact same thing. The second, however is
written completely in terms of function composition and application.
The s in the first implementation is what's being referred to as a
'point'.
On 12/14/06, Steve Downey
i'm not naive enough to think they are the composition function, and i've gathered it has something to do with free terms, but beyond that i'm not sure. unless it also has something to do with fix points? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (9)
-
ajb＠spamcop.net -
Andrew Wagner -
Arie Peterson -
Cale Gibbard -
Dan Piponi -
dons＠cse.unsw.edu.au -
Justin Bailey -
Scott Brickner -
Steve Downey