The Artima Developer Community
Sponsored Link

Weblogs Forum
Typing like a Functional Programmer

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

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
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 4:54 AM
Reply to this message Reply
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.


Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: Typing like a Functional Programmer Posted: Nov 26, 2006 5:29 AM
Reply to this message Reply
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 2:52 PM
Reply to this message Reply
> 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 2:36 PM
Reply to this message Reply
"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 3:32 PM
Reply to this message Reply
> "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 4:03 PM
Reply to this message Reply
> "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?

http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html#add(java.math.BigInteger)

Andrew Chase

Posts: 5
Nickname: acechase
Registered: Jul, 2003

Re: Typing like a Functional Programmer Posted: Nov 27, 2006 4:13 PM
Reply to this message Reply
> 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.

Morgan Conrad

Posts: 307
Nickname: miata71
Registered: Mar, 2006

Re: Typing like a Functional Programmer Posted: Nov 27, 2006 5:47 PM
Reply to this message Reply
> 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.

Morgan Conrad

Posts: 307
Nickname: miata71
Registered: Mar, 2006

Re: Typing like a Functional Programmer Posted: Nov 27, 2006 5:52 PM
Reply to this message Reply
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_So mething_else_happens.

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?

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Typing like a Functional Programmer Posted: Nov 27, 2006 6:03 PM
Reply to this message Reply
> 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?

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 8:43 PM
Reply to this message Reply
> > 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 x = x + 5

Dave Gauthier

Posts: 1
Nickname: babar
Registered: Apr, 2004

Re: Typing like a Functional Programmer Posted: Nov 27, 2006 11:33 PM
Reply to this message Reply
> > 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.

Does that help at all?

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Typing like a Functional Programmer Posted: Nov 28, 2006 12:47 AM
Reply to this message Reply
> > 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.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Typing like a Functional Programmer Posted: Nov 28, 2006 12:53 AM
Reply to this message Reply
> 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

Does that help?

Sean Conner

Posts: 19
Nickname: spc476
Registered: Aug, 2005

Re: Typing like a Functional Programmer Posted: Nov 28, 2006 2:06 AM
Reply to this message Reply
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 [ 1  2  3  4 | » ]
Topic: Typing like a Functional Programmer Previous Topic   Next Topic Topic: My Own Personal Blog


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us