Hacker News new | past | comments | ask | show | jobs | submit login
A practical introduction to functional programming (maryrosecook.com)
240 points by danso on Jan 25, 2015 | hide | past | web | favorite | 62 comments

> Ignore all that. Functional code is characterised by one thing: the absence of side effects. It doesn’t rely on data outside the current function, and it doesn’t change data that exists outside the current function. Every other “functional” thing can be derived from this property.

This. So much this. I'd go even further and say functional programming is just like imperative programming but without variables (except for those passed in as arguments). This has always struck me as the key difference between the two. The rest (first class / higher order functions, mapping, reducing, pipelining, recursing, currying etc) in my opinion is just making things more convenient in functional languages, dealing with this absence of variables.

The key achievement of functional programming in my opinion is then the provision of special tools (see above) that help programmers solve particular problems in particular efficient ways, that programmers would have solved by using variables in a possibly less efficient way in an imperative language. In short functional programming forces the user to pick the right tool for the task.

Eh, I think that leaving out first-class functions is unforgivable. The complete spirit of functional programming can be neatly summed up as:

"Functional programming is the creation of useful programs using only functions mapping input arguments (perhaps themselves functions!) to outputs (also perhaps functions!) without external state."

You can't leave out the function part of functional programming.

I would agree with GP that emergent code organization principles that come from eliminating side effects are the crux of FP, as far as being the bottom line of what makes it effective and worth internalizing.

Higher-order functions are a simple and powerful form of abstraction, but not much else. I could imagine something which has the software engineering benefits of an FP language without HOF, although maybe it wouldn't culturally be one.

I think getting enthusiastic about higher-order functions and trying to use them in OO languages can range from good to neutral to bad. On the plus side, code is usually shorter. On the negative side, it's not necessarily more readable, and types still usually expose the same amount of information about their inputs/outputs, which is "call me, anything can happen" (plus plenty of opportunity for lazy side effects, the most confusing kind).

This kind of becomes a name game, what is truly "FP". For many, FP is meaningfully defined as a focus on functions and it's silly to try to define that away.

There is something, "ML-alike FP" or, even, "Haskell-alike FP" which I might call "pure FP" which is what you say. This is less difficult to see as being centralized on purity more than "FP" at large. Presumably, you could have "pure" OO, classes and all, by eschewing effects just the same.

I have at least one bet in the pot that you cannot, though. I think the true beating heart of "pure FP"/"Haskell-alike FP" is the centricity of composition as a guiding design of language. This comes directly from some of the category theoretic heritage of the core languages here. Once you're here, the primality of functions themselves is hard to escape from. You can go a ways without HOFs, but the lack of richness of composition which you're stuck with is very painful. BiCCCs are a very sweet spot.

But a function isn't really a function unless it is referentially transparent. Having HoF, composability, etc.. is all a direct result of referential transparency.

Sure we can simulate these concepts in imperative languages, but the broken abstractions break down rather quickly since the laws are ignored.

It's just a function in a different, less observable category. That's not the worst thing. And, of course, I'd like to argue for "pure FP" too.

Really, I just want to sidestep the argument that is appearing all over this post: that "FP" is also this, and this, and this.

Sure. FP is terrifically poorly defined. The definition used in the article is rather more specific than what most people would say. But it has merits and should be discussed. Let's just not stumble over naming difficulties to do so.

So, I see what you're saying, but I maintain that without first-order functions, you can't do anything useful with code organization.

If you wanted to simulate that, imagine writing in C or C++ or Javascript using only functions, only returning copies of things changed by the function, and never referencing global state.

There's nothing particularly magic about that, other than better testability--it's just really slow and obnoxious imperative code. When you start passing around functions and currying values, though, then you're actually starting to see cool things happening.

I think you're making this too abstract to be understood without having already seen the light, perhaps an example would help?

Okay, sure, let's look at it in Javascript.

The task? Take a list of numbers, and produce a list containing only the squares of those numbers--and only those squares falling between 10 and 50.

  var inList = [1,2,3,4,5,6,7,8,9,10];
  var non_fp = function ( myListOfNumbers ) {
  	var out = [];
  	var temp = [];
  	var i = 0;
  	var j = 0;
  	// square the numbers
  	for (i = 0; i < myListOfNumbers.length; i++) {
  		temp.push( myListOfNumbers[i] * myListOfNumbers[i] );
  	for (j = 0; j < temp.length; j++) {
  		if ( temp[j] > 10 && temp[j] < 100 ) {
  			out.push( temp[j] );
  	return out;
  var fp = function ( myListOfNumbers ) {
  	return myListOfNumbers.map( function (x) { return x*x; } )
  			      .filter( function (x) { return (x > 10)  && (x< 100); });
The first has no side effects.

The second version has no side effects, and wouldn't be possible without first-class functions, and to me is clearly the more functional answer.

Suggested minor change to the non_fp one:

  var inList = [1,2,3,4,5,6,7,8,9,10];
  var non_fp = function ( myListOfNumbers ) {
  	var out = [];
  	// square the numbers
  	for (var i = 0; i < myListOfNumbers.length; i++) {
  		var x = myListOfNumbers[i] * myListOfNumbers[i];
                if (x > 10 && x < 100) {
                        out.push( x );
  	return out;

That's a correct change--I chose the implementation that I did so that it was very obvious how the things remap to a "functional" approach. :)

You see the point I'm driving at, though?

(and thanks for prodding me into writing code to illustrate things better)

> You see the point I'm driving at, though?

Yes, absolutely. I thought you were right on the money with the words but I figured a bit of code would do wonders to hammer it down.

Erlang does an even better job I think:

  [X * X || X <- lists:seq(1,10), X * X > 10, X * X < 100].

  [Y || Y <- [X * X || X <- lists:seq(1,10)], Y > 10, Y < 100].
Slightly longer, but without that X * X repetition.

Yep. Erlang/Elixir is actually kind of a joy to work in for math stuff. Shoot me an email if you'd like to chat about that.

I'm slowly slogging my way through Project Euler in Erlang, it's my default way of learning anything new and so far I've been making progress but I'm pretty sure that what I'm writing is absolutely horrible non-idiomatic erlang. I will probably take you up on that but after I've learned a bit more so at least I stand half a chance of understanding you.

I am probably making a similar point to "gracenotes" here, but as I see it the functions in functional programming are simply a tool that can be used in order to achieve side effect free programming. They are not what really defines functional programming as a concept, even though they share the root name "function".

Yep. It always amazes me when die-hard OOP'ers get it all wrong and think FP is at war with their beloved OO. Well no. Plenty of FP languages exist that combine FP and OO together. Scala.. F#.. OCaml.. etc.

It always amazes me when die-hard FP'ers get it all wrong and think OOP is at war with their beloved FP. Well no, plenty of OOP languages exist that combine FP and OO together. Scala.. C#.. Clojure.. etc.

C# at least doesn't do immutability per default, which is another classical property of FP.

Most functional programming languages don't do immutability by default (which anyways, is an aspect of the library that can choose to be or not to be; LINQ definitely is). There are also no true scotts men.

Considering there is no (AFAIK) agreed upon definition of what an FP language is, I'm using classical as "common and found in older FP languages", not saying that an FP language which isn't immutable per default is not FP.

I'm think of Haskell, OCaml or (AFAIK) Erlang. From what I read, Clojure has also a lot of emphasis on immutability.

Haskell and OCaml aren't really that old. I'm thinking ML and Lisp, scheme, which don't focus on immutability.

Both clojure and haskell have mutability, just at differing granularities (haskell monads, clojure replace the world object). They can do it with referential transparency though (which is probably your meaning, obviously pure immutability is impossible and not sensical).

Haskell is from 1990 and OCaml from 1996, it's not awfully recent.

> Both clojure and haskell have mutability, just at differing granularities (haskell monads, clojure replace the world object). They can do it with referential transparency though (which is probably your meaning, obviously pure immutability is impossible and not sensical).

Well, you have to have to be able to manipulate state somehow (even if, at least on the surface, the state monad emulates mutability, as opposed to, eg, OCaml's notion of mutation, which is very explicit in what it does). But the point is that it is not the path of least resistance in these languages.

They are not very old either, at least not compared to Lisp (60s), scheme and the MLs (70s/80s). Haskell is quite brand spanking new in comparison to the old guard.

What C# lacks for me in FP, case matching, has little to do with purity. The FP story involves purity but is not dominated by it. List comprehensions still work in C# even though you can theoretically side effect in your select and filter functions.

Perfect example ^

Did you just illustrate his point? No one in the comments mentioned OOP and you were the one to bring it up to disparage it. He was just responding to your hypocrisy.

"Bring it up to disparage it"... uh what?

You've got it wrong. OOP'ers have no problem using FP. It is die-hard FP'ers who would disparage OOP whenever given the chance.

I think you're right. OOP'ers tend to not understand FP, and when they do get it, they are happy to use it. On the other hand, die-hard FP'ers tend to look down on OOP'ers.

I'd bet many FP'ers don't really understand OOP either. They tend to think creating complex hierarchies is necessary and algebraic data types and modules magically fix everything.

How many functional programming languages do you cross of the list of functional programming languages if you make that claim? At the very least anything Lisp related, all the ML languages as well. You are pretty much left with Miranda, Haskell, and a few related languages.

An FP language doesn't preclude non-FP code, just like OOP doesn't preclude ... procedural code? I'm not sure what the opposite would be but it exists (think Matlab code).

I would argue that the lisps are not very functional languages (both in the importance of effects and the style of code I've seen written in lisps), but Scala provides for a lot of FP assurances (val over var, good FP-y libs), and people in the community value effectlessness. So I'm comfortable calling Scala a FP language.

>You are pretty much left with Miranda, Haskell, and a few related languages.

Agda and Idris as well.

The bar for what constitutes "FP" has been changing since the 50s. Doesn't sound unreasonable to me.

Functional programming used to mean programming with first class functions and closures; they even put it in the name "functional"al programming (just like OOP meant program with objects, whether this involved classes or not).

So that is Lisp, the first FP in the 60s, and then the MLs of the 70s/80s. They knew about purity, and even preferred it (for things like list comprehensions, it is very useful), but were never very dogmatic about it.

Would concatenative languages apply ?

I found Higher Order Perl as a good tutor as well: http://tinyurl.com/orwm2ed

It's worth noting that things like print and random are just as much side effects as mutability. To eliminate random is easy: realize that random generation is a function from a hidden random generator state to a "random" value and a new random generator state. Now use state-minimization techniques.

To eliminate print is much harder.

print is IO so of course it is hard to eliminate side effects.

IO monads aren't the only way. If all you want is print it's even quite easy.

Please do tell or link to more, if you're willing!

Print alone is easy as you can just have functions output both their normal output and a listing of whatever they printed. These listings then get concatenated together (this is technically "the writer monad", but you don't need to know as much).

IO was originally handled in Haskell as `main :: [String] -> [String]`. More generally, we might think `main :: [Input] -> [Command]`. This is obviously a pure function. If the types Input and Command are a bit like

    Input   = SawChar Char   | Tick UTCTime | FileRecv String
    Command = PrintChar Char | RequestTime  | RequestFile FilePath
you can imagine how a more general effects framework could be done purely.

In practice, monads are a lot simpler than this. In particular, it can be easy to get desynchronized from your Commands and Inputs.

Other language have more explicit effect typing as well. Conor McBride's `Frank` comes to mind, but it's fairly complex.

Yes, but you can uncouple the API talking about and generating IO actions from the performance of those IO actions if you have a pure, lazy language.

The lambda syntax seems like a major shortcoming in Python's readability. It uses the comma in its declaration and then the comma is used again a separator for the arguments being passed into the outer function (reduce in this case). I feel their should be better visual indication for when you are out of the lambda part.

Isn't the colon an adequate indicator that you have left the anonymous function declaration?

Seems somewhat perverse to do this in python, and never once mention list/generator comprehensions.

I get that this isn't a guide for using functional programming in python, but rather a guide for using functional programming in non-python languages, shown with examples in python. But practically, who's the audience for that?

I am. I know python quite well, but I did not understand functional programming before I read this article. Oh sure, I'd looked it up on wikipedia, and read a few blog posts, and perused a Haskell tutorial, but none of that made it click. Too many new concepts at once. Using python as the instructive language is great simply because many people know python, and for those who don't, the syntax is easy to follow.

This article was perfect for me. The "guide rope" paragraph instantly clarified and put into context all the other disjoint pieces of information that I had picked up.

I can now see how to apply these concepts in almost any language. Right away, I can see how to refactor my side-effect-riddled C++ to make it more suitable for unit tests.

I came across this piece after following a previous story on HN, and was very tempted to post it at the time, because it really helped me.

It really is an excellent introduction to FP, but:

> I know python quite well, but I did not understand functional programming before I read this article

Sounds like someone who would have benefitted from practical uses of FP in python, such as comprehensions.

...It's a really neat article, but I think it would have been considerably improved with asides for "And here's an even cleaner way to write this, if you're using python"

I do know list comprehensions, and I use them all the time (not trying to be defensive here, just providing context). I understand that they are just a different syntax for mapping -- applying a function to members of a list to produce a new list. However, while list comprehensions are clean and pythonic syntax, I think the "map" syntax more clearly illustrates the concept that the author is trying to teach.

Your suggestion for asides is certainly valid, and I agree would make it more useful for budding pythonistas. I just think that her focus was to introduce functional concepts, and python was simply an easy language to make the concepts concrete. I think that it's stretching the scope of the article, and therefore watering down its message, to put any additional focus on specific features of the python language.

I guess this is an example of my earlier point: I knew about map and reduce, and understood their power. However, it had not clicked for me before reading this article that they feature so prominently in functional programming because they work with functions that have no side effects.

I thought leaving out list comprehensions was an excellent idea - it is a construct that few programmers from other languages would understand, and would have caused parts of the article to turn into a python tutorial. As it is, the python is close enough to universal pseudo-code.

If I was going to claim it was perverse I would say it is a little perverse to teach FP concepts in a language that doesn't support tail call optimisation. Eventually someone who tries to apply this rigorously is going to get an unpleasant surprise in Python. But since it is more about explaining principles than language details I would give it a pass on that anyway.

> But practically, who's the audience for that?

Anybody that would benefit from re-using some of the lessons from functional programming such as side-effect free programming, splitting pure and stateful code and so on (though some of the examples could do this better than they do now it is a step in the right direction).

Python, PHP, Java, Ruby and C programmers could learn quite a bit from this.

It's a well-written and nice article, but just kinda weird in spots, saying that the code is more self-evident and readable, whereas I think it's sometimes making a language do something it only does with considerable strain.

Insofar as python is essentially pseudocode, I can get the appeal of writing non-pythonic python, but ... it strains it a bit to do this for such extensive use of lambda, the most awkward bit of syntax in python, one that almost always has more readable alternatives.

Any time I see a use for lambda (typically only with the functional builtins), I just write a function instead. Two extra lines are worth it for the readability alone. You can also reuse a function, which makes more sense to me than potentially writing the same lambda multiple times.

I do like that the author used Python, even if it was only for the purpose of pseudocode. Python is, after all, "executable pseudocode". It's also the only language I really know in-depth.

Interestingly, at least at the places I've worked at recently, that functional "style" or kernel of truth is being picked up by more and more PHP programmers. It's great, makes it far easier to test code.

I can see the value in not using Python's comprehensions because although they provide an easy way to write map and filter, there's no clean, consistent way of expressing fold (or reduce or whatever you want to call it) - at least, not without altering state, which flies in the face of what this tutorial is trying to teach. Since those are the big three, I can see the value of writing everything with lambdas in the tutorial just to keep things consistent.

That said, I agree that it would have been helpful to at least give a mention to list/generator comprehensions.

This would show that with proper language support FP could be much more pleasant. Who would want to try and apply ideas from this worderful article to, say, her everyday C++ coding? After seeing something like squares=[x*x for x in range(10)] she would write exactly WHAT in C++?

JS would probably have been a better language for a few reasons:

- braces denote function bodies, even if you don't code it's pretty obvious.

- no strange difference between lambda and def, a function is a function

Because the purpose is to demonstrate the use of functions. * comprehensions are syntactic sugar above them and would hide their true nature.

I think the same article was on hacker school website also?

Yes, since the author works at Hacker School.

So clearly written. Thank you.

Applications are open for YC Winter 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact