Summary
For a long while I didn't fully grasp the funky syntax of typed functional languages like ML and Haskell, until I realized a fundamental difference between many typed functional languages and common imperative languages.
Advertisement
This purpose of this blog entry is to help programmers more familiar with imperative languages like C++, C# and Java to make the transition to programming in a typed functional language like OCamL, Haskell, or F#.
An imperative programmer would normally think of integer addition as being a function which takes two integers and produces a new integer. You could write this concept as follows:
add_ints : (int, int) -> (int)
Now ask yourself what happens if you pass only one integer to an integer addition function? In most imperative languages it simply fails to compile, but in functional land the answer is: you get a new function.
This new function takes a single integer and returns a single integer. Using the earlier type notation this alternative view of integer addition could be written as:
add_ints : (int) -> ((int)->(int))
This is a key concept in functional languages called currying. An integer addition function either returns an integer if it gets two integers, or it returns a function which takes a single integer and returns an integer.
When you think about it this way, you may realize that the first way of understanding add_ints can be replaced by the second. Consider:
add_ints(x, y) = add_ints(x)(y)
This approach can be generalized if a language enforces the rule that all functions of more than one parameter are functions which take one parameter and return another function.
With that generalization then you might realize the parantheses are unneccessary in both calling the function and expressing the type. For example:
add_ints : int -> int -> int
add_ints x y
This is now almost exactly what you would write in a typed functional language like ML, OCaml, or Haskell.
This might take some time to digest (it did for me, but I'm not really that bright), but hopefully it might help illuminate your way through the tangled woods of typed functional programming.
> I'm surprised that you didn't mention what that is called. > It's called 'currying'.
I was debating that. I suppose in retrospect it is weird to leave out the terminology, but my thinking (flawed as it may be) was that the extra terminology causes a panic response in many programmers.
I'll edit the article to reference the term "currying". Thanks for pointing that out.
> "This new function takes a single integer and returns a > single integer" > > Sorry, but this is not helpful. Just what integer does it > return?
function add_five = add_ints(5) int x = add_five(3) // x == 8
> How do I write a unit test? :-)
I am not sure what you would want to test in such a trivial case.
> Since the function is named "add", passing it one argument > is non-sensical.
I know it may seem non-sensical, but the definition of passing one argument to any two-argument function in a functional langauge is to return a function which requires the missing argument. Does this make more sense?
> "This new function takes a single integer and returns a > single integer" > > Sorry, but this is not helpful. Just what integer does it > return? How do I write a unit test? :-) > > Since the function is named "add", passing it one argument > is non-sensical.
> Since the function is named "add", passing it one argument > is non-sensical.
on the contrary, passing it one argument is not non-sensical at all, once you've adopted the functional paradigm. Passing a function called add a single argument, let's say 5, would then produce a new function, which will add 5 to the single integer argument it is passed. The example, in pseudo-code, would be like this:
add5 = add 5 //5 is now "curried" to the first argument result = add5 100 //result now equals 105.
Partially parameterized functions can be useful in lots of other situations beyond this trivial example.
> function add_five = add_ints(5) > int x = add_five(3) // x == 8
o.k., now I'm really confused. This function has STATE. It is an Object, not a Function. I thought the big advantage of FP was no states, no threading issues, etc. I guess I'm missing something fundamental about FP.
BigInteger is an Object. So add makes sense there.
> > function add_five = add_ints(5) > > int x = add_five(3) // x == 8 > > o.k., now I'm really confused. This function has STATE. > It is an Object, not a Function.
It does not have mutable state.
Consider how it is similar or dissimilar to a function defined like this
> > function add_five = add_ints(5) > > int x = add_five(3) // x == 8 > > o.k., now I'm really confused. This function has STATE. > It is an Object, not a Function. I thought the big > g advantage of FP was no states, no threading issues, etc. > I guess I'm missing something fundamental about FP. > > BigInteger is an Object. So add makes sense there.
The function does not retain state - it returns a new function.
Think of functions as objects - add_ints returns an int if it receives 2 ints, or a new function object if it receives one int. The new function it returns doesn't have state, it is just doing something different - adding a pre-defined int to the argument. The original function does not change, and the new function does not change after it is created.
> > function add_five = add_ints(5) > > int x = add_five(3) // x == 8 > > o.k., now I'm really confused. This function has STATE. > It is an Object, not a Function. I thought the big > g advantage of FP was no states, no threading issues, etc.
That is correct, pure FP doesn't rely on mutable state. I don't know about the "threading issues", that's a whole other kettle of fish.
> I guess I'm missing something fundamental about FP.
I am really glad you are asking these questions, because it is a surprisingly small but important step one needs to take before "getting" functional programming.
Technically the function doesn't have state any more than the function below has state:
int add_five(int x) { return x + 5; }
Your intuition about the similarity of higher order functions and an object is very accurate. You can implement curried functions using objects.
In fact in C++, an object which overloads the "()" operator is virtually the same thing as a function.
> Also, the function is named > > add_ints > > Passing it a single argument simply confuses. > > Maybe you should call it > add_two_ints_and_return_an_int_unless_you_pass_in_only_one > _int_in_which_case_Something_else_happens.
Well yeah, you could :-)
> Bye the way, if I go > > add_ints(5); > add_ints(6,7); (pardon me mashing the syntax) > what gets returned? 18 or 13? And how do you know?
Each call to add_ints returns a brand new function created out of thin air.
So to expand your example:
function f = add_ints(5); // f isn't used int n = add_ints(6, 7); // 13
Okay, lets see if I got this. I have a function called add() which takes two parameters x and y and returns the sum of the two parameters.
a = add(3,4); // a is now 7
But, if I only give it one parameter, instead of failing, or giving a compiler error, it generates a new function that adds a constant (given as the single parameter) to its parameter.
f = add(5); a = f(2); // a is now 7
So I assume this binding would be to the first parameter, so that:
a = sub(7,2); // a is now 5 f = sub(3); b = f(7); // b is now 4
Have I got it?
Flat View: This topic has 51 replies
on 4 pages
[
1234
|
»
]
Previous Topic
