Weblogs Forum
Typing like a Functional Programmer

51 replies on 4 pages. Most recent reply: Dec 8, 2006 2:16 PM by Paul Berg

 Previous Topic Next Topic
 Flat View: This topic has 51 replies on 4 pages [ 1 2 3 4 | » ]
 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Typing like a Functional Programmer (View in Weblogs)
Posted: Nov 26, 2006 1:54 AM
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.
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
```
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.

 Michael Feathers Posts: 448 Nickname: mfeathers Registered: Jul, 2003
Re: Typing like a Functional Programmer Posted: Nov 26, 2006 2:29 AM
I'm surprised that you didn't mention what that is called. It's called 'currying'.

 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Re: Typing like a Functional Programmer Posted: Nov 26, 2006 11:52 AM
> 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.

 Morgan Conrad Posts: 307 Nickname: miata71 Registered: Mar, 2006
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 11:36 AM
"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.

 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 12:32 PM
> "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?

 James Watson Posts: 2024 Nickname: watson Registered: Sep, 2005
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 1:03 PM
> "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.

Just like this, right?

 Andrew Chase Posts: 5 Nickname: acechase Registered: Jul, 2003
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 1:13 PM
> 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 argumentresult = add5 100   //result now equals 105.`

Partially parameterized functions can be useful in lots of other situations beyond this trivial example.

 Morgan Conrad Posts: 307 Nickname: miata71 Registered: Mar, 2006
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 2:47 PM
> 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.

 Morgan Conrad Posts: 307 Nickname: miata71 Registered: Mar, 2006
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 2:52 PM
Also, the function is named

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_So mething_else_happens.

Bye the way, if I go

add_ints(6,7); (pardon me mashing the syntax)
what gets returned? 18 or 13? And how do you know?

 James Watson Posts: 2024 Nickname: watson Registered: Sep, 2005
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 3:03 PM
> Bye the way, if I go
>
> add_ints(6,7); (pardon me mashing the syntax)
> what gets returned? 18 or 13? And how do you know?

I'm not a functional developer but these are two unrelated calls (in anything I've seen, unless it's some sort of perl-ish nightmare).

So the first call returns (int)->int
and the second call returns int.

The idea is that you can pass in one int and pass that to a something that takes a function with a single int parameter.

The BigDecimal example was meant to demonstrate that the functional and OO paradigms aren't as far apart as people tend to believe they are, IMO.

Interesting thought about the function holding state. I can't really argue otherwise but I'm sure someone will take issue with that.

 Isaac Gouy Posts: 527 Nickname: igouy Registered: Jul, 2003
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 5:43 PM
> > 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 x = x + 5`

 Dave Gauthier Posts: 1 Nickname: babar Registered: Apr, 2004
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 8:33 PM
> > 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.

Does that help at all?

 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 9:47 PM
> > 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.

 Christopher Diggins Posts: 1215 Nickname: cdiggins Registered: Feb, 2004
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 9:53 PM
> Also, the function is named
>
>
> Passing it a single argument simply confuses.
>
> Maybe you should call it
> _int_in_which_case_Something_else_happens.

Well yeah, you could :-)

> Bye the way, if I go
>
> 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.

function f = add_ints(5); // f isn't used
int n = add_ints(6, 7); // 13

Does that help?

 Sean Conner Posts: 19 Nickname: spc476 Registered: Aug, 2005
Re: Typing like a Functional Programmer Posted: Nov 27, 2006 11:06 PM
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 5f = sub(3);b = f(7); // b is now 4`

Have I got it?

 Flat View: This topic has 51 replies on 4 pages [ 1  2  3  4 | » ]
 Previous Topic Next Topic