Computer Science Canada Challenge for 2011: functions |
| Author: | wtd [ Sat Jan 01, 2011 2:03 am ] |
| Post subject: | Challenge for 2011: functions |
After a quick chat with Tony, I'm posing this challenge for compsci.ca members in 2011: simply, come to grips with the following assertion. Functions can only take one argument. |
|
| Author: | apython1992 [ Thu Mar 03, 2011 1:13 pm ] |
| Post subject: | Re: Challenge for 2011: functions |
Hmmm, I haven't started yet with learning functional programming (so excuse my ignorance here  ) but assuming functions have the same behaviour, is it something like a single array of arguments is passed in (and thus one overall argument) and thereafter individual parameters are accessed by simply indexing the array? Or is it more complex than this? |
|
| Author: | bbi5291 [ Thu Mar 03, 2011 1:55 pm ] |
| Post subject: | Re: Challenge for 2011: functions |
The challenge isn't so much how to write code using functions that only take one argument (yes, it is true that you could just stuff all the arguments in an array), but rather how to conceive that a function, even when it appears to be taking two or more arguments, can be deconstructed so that it only takes one at a time. Besides, what about the function that you use to create the array? Isn't that, in a sense, taking multiple arguments? |
|
| Author: | Tony [ Thu Mar 03, 2011 1:59 pm ] |
| Post subject: | RE:Challenge for 2011: functions |
Arrays work with fixed-width elements only, but arguments could be primitives, objects, or other functions. |
|
| Author: | apython1992 [ Thu Mar 03, 2011 2:16 pm ] |
| Post subject: | Re: Challenge for 2011: functions |
Oh yeah, I know that the challenge isn't about how to write that code, I was just guessing that maybe internally that's how the arguments are dealt with - a single array of objects, for example. But now that you mention that about deconstructing the function to take only one argument... I'm thinking that functions that take multiple arguments can be written as something like a chain of functions that each take one argument. So for example, instead of having a single function that takes two integers and returns the sum, such as f(x, y) = x + y you could have functions nested together, for example f(x,y) = g(f(x),y) = x + y where first, x is inputted and f(x) would just return x. This means that really only one argument is dealt with at a time, because f(x) must be evaluated before calling g(f(x),y). Thus, because x has a value, g really only takes one value in, y. So basically, f(2) would return 2, which means g(y) is now defined as 2 + y. Is this correct? |
|
| Author: | bbi5291 [ Thu Mar 03, 2011 3:41 pm ] |
| Post subject: | Re: Challenge for 2011: functions |
You're on the right track, but the following notation may be more appropriate: f(x,y) = (g(x))(y), to emphasize the fact that the output of g(x) is itself a function, which is then applied to y. |
|
| Author: | apython1992 [ Thu Mar 03, 2011 4:01 pm ] |
| Post subject: | Re: Challenge for 2011: functions |
I see...so upon calling g(x), instead of just returning x, it would return a new function that is defined as x + y (x now being a value), taking y now as its only argument? So step by step it would look something like: f(5, 13) = [g(5)](13) = 5 + 13 = 18 |
|
| Author: | Shanethe13 [ Wed Mar 09, 2011 9:46 pm ] |
| Post subject: | RE:Challenge for 2011: functions |
Apython, you are exactly right, and the term for what you just described is currying, named after none other than Haskell Curry! Time for a crash course in Haskell to demonstrate! Haskell function declarations have two parts, a type signature, and a binding. The binding is where stuff actually happens (or rather doesn't happen depending on your philosophy), but it is the type signature which tells you exactly what it is that a function does. For example, a function that adds two numbers might be described as: add :: (Integer a) => a -> a -> a add x y = x + y This reads that the function, add, takes two arguments of type Integer, and returns a third value of type Integer. However, there's a catch! Functions only take one argument, and so while this type signature describes what is happening, it isn't entirely accurate. Rather, it should be rewritten as this: add :: (Integer a) => a -> (a -> a) Whereas the first signature made it seem like the function accepted two arguments, and returned a third integer, this one shows what is really happening: the function, add, accepts an integer, and returns a second function which accepts an integer, returning the final answer. If we called the function like this: add 5 7 We are actually doing: (add 5) 7 Where (add 5) evaluates to a function which accepts one parameter and adds five to it. You seemed to grasp the concept from your last post, so none of this should be new to you. I just thought I'd type up a more formal explanation while waiting in this airport  |
|
| Author: | apython1992 [ Wed Mar 09, 2011 11:04 pm ] |
| Post subject: | Re: Challenge for 2011: functions |
Good stuff! I do understand the concept, but my next question is: why? Is it necessary for computers to take this route? If so, why? |
|
| Author: | Shanethe13 [ Wed Mar 09, 2011 11:25 pm ] |
| Post subject: | Re: Challenge for 2011: functions |
apython1992 @ Wed Mar 09, 2011 11:04 pm wrote: Good stuff! I do understand the concept, but my next question is: why? Is it necessary for computers to take this route? If so, why?
I don't have a good answer for you off of the top of my head, but it is extremely useful for higher-order functions. Without giving a concrete example, I can just say that currying is normally used to dynamically create functions, which can then be used as building blocks to make more functions. You can do some really interesting stuff by partially applying a function, then using the result to map over a list. Wtb or Bbi might be able to explain the purpose to you a bit better, I'm nowhere near fluent in this stuff. |
|
| Author: | Tony [ Wed Mar 09, 2011 11:35 pm ] |
| Post subject: | RE:Challenge for 2011: functions |
Because in Math, when you want to completely understand a system and be able to do various proofs on it, it's often advantageous to have everything build out of as few basic blocks as possible. functions with n arguments == function with exactly one argument * currying transformation. http://en.wikipedia.org/wiki/Currying#Mathematical_view Quote: In theoretical computer science, currying provides a way to study functions with multiple arguments in very simple theoretical models such as the lambda calculus in which functions only take a single argument. |
|
| Author: | bbi5291 [ Thu Mar 10, 2011 12:08 am ] |
| Post subject: | Re: Challenge for 2011: functions |
This may only be tangentially related, but an interesting note is that math doesn't even really have a notation for functions of multiple variables. I mean, it seems as though you can write the type of, say, a real-valued function of a single real variable as f : R -> R, and the type of a real-valued function of two real variables as f : R^2 -> R, but R^2 actually represents the Cartesian product of R with itself, that is, the set of pairs of reals, so that f(x,y) should really be thought of as f((x,y)), where (x,y) is the independent variable. (Also, in Haskell, there is a function "curry" that takes a function on pairs and converts it into an equivalent curried function, i.e. a f : R^2 -> R would become f : R -> (f : R -> R), and "uncurry" that accomplishes the opposite transformation.) |
|
| Author: | apython1992 [ Thu Mar 10, 2011 9:51 am ] |
| Post subject: | RE:Challenge for 2011: functions |
Very neat. So when wtd says that functions can only take one argument, does this mean that in computation, functions are always internally broken down this way? Or is this currying only used for lambda functions? |
|
| Author: | Tony [ Thu Mar 10, 2011 10:23 am ] |
| Post subject: | RE:Challenge for 2011: functions |
Not _always_. For example, in assembly there are no arguments at all. You just jmp to a location and read from some registers. Conceptually that's a function call. |
|
| Author: | DtY [ Thu Mar 10, 2011 6:23 pm ] |
| Post subject: | Re: RE:Challenge for 2011: functions |
apython1992 @ Thu Mar 10, 2011 9:51 am wrote: Very neat. So when wtd says that functions can only take one argument, does this mean that in computation, functions are always internally broken down this way? Or is this currying only used for lambda functions? Haskell functions are; syntactically at least. I doubt that a good compiler like GHC would actually compile the functions like that except when you're currying them. Only allowing single argumented functions is useful (for the reasons described above), but it would be pretty inefficient to have to construct a new lambda function every time you call a multi?rgument function. |
|
| Author: | apython1992 [ Sat Mar 12, 2011 10:39 am ] |
| Post subject: | RE:Challenge for 2011: functions |
Hm, okay yeah that makes sense. I'm gonna spend some time learning Haskell, I think. It sounds like a pretty interesting language. |
|
| Author: | Insectoid [ Sat Mar 12, 2011 12:51 pm ] |
| Post subject: | RE:Challenge for 2011: functions |
Don't be so rash. Your sanity is at stake! |
|
| Author: | apython1992 [ Sat Mar 12, 2011 3:30 pm ] |
| Post subject: | Re: RE:Challenge for 2011: functions |
Insectoid @ Sat Mar 12, 2011 12:51 pm wrote: Don't be so rash. Your sanity is at stake!
Haha, you're probably right. |
|
| Author: | Tyr_God_Of_War [ Sun Apr 24, 2011 8:09 am ] |
| Post subject: | Re: Challenge for 2011: functions |
One really nice thing about this is when you are mapping over a list. >map (+3) [1,2,3] [4,5,6] Compare that to in scheme: >(map (lambda (x) (+ 3 x)) '(1,2,3)) '(4,5,6) Quite a bit shorter and nicer on the eyes too. (Not that I have anything against scheme mind you. It's a great language, but Haskell is just prettier) |
|
| Author: | wtd [ Thu May 05, 2011 10:20 am ] |
| Post subject: | Re: RE:Challenge for 2011: functions |
Insectoid @ Sun Mar 13, 2011 1:51 am wrote: Don't be so rash. Your sanity is at stake!
If you're on this site, it's a good bet your sanity is already questionable at best. |
|