This is not true at all. The only technical requirement for you to follow the functional paradigm is immutability.
Keep in mind that passing a first class function into another function as a parameter is not that far off from passing the result of that function as a parameter.
You can still use recursion to loop. First class functions are a convenience to functional programming not a requirement. Map and reduce and other higher order functions are also not a strict requirement for fp.
Without first class functions an immutable program can still be turing complete. I would say that if a language only supports recursion and is immuteable, then that is all you need for the language to be part of the fp paradigm.
Intuition and experience. The definition naturally occurs to you over time, I've never seen the isomorphism between immutability and functional expressions illustrated though. However, it is explicit that every functional language is immutable as a requirement.
I'm sorry to say that if you don't understand this, you haven't really understood what functional programming is... You're just a guy who understands higher order functions.
> The only technical requirement for you to follow the functional paradigm is immutability.
So are you saying that for instance both CaML and LISP aren't FP ? Because both are certainly not about immutability and you can write mutable messes in either.
"In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. It is a declarative programming paradigm, which means programming is done with expressions[1] or declarations[2] instead of statements."
Key phrase: "avoids changing-state and mutable data."
You can use C++ as if it was a functional language just like you can use LISP and CaML as if variables were mutable. However in both cases you are bending the language to follow a paradigm that is NOT functional.
"passing a first class function into another function as a parameter is not that far off from passing the result of that function as a parameter"
Not that far off unless you want to do partial application, currying, lazy evaluation, analyze, or change the code of the function before actually using it.
Like the article said, "functional programming" doesn't mean using maps and folds. Functional programming is meant to make you reason about state by always handling it very explicitly e.g. by using functions that take a state and produce a new one, so that your program is constructed by piping the result of a function into another's input, instead of implicitly.
That would appear to be a definition of functional programming that says nothing about functions themselves, which seems odd. Because you can't make any guarantees about state in a language that wasn't intended for FP because how do you know what side effects the built-in functions are having?
Well, clearly in a language that doesn't make a distinction between functions that have side effects and functions that don't you'll just have to pinky swear you won't put any in your functions, and maybe try to wrap the side effects the built-in functions do have (like errno in C) with your own functions.
But that's not the point; a functional style can be achieved in any language as long as it has functions.
You can't even make that guarantee for functional languages. How do I know the built in operators for scala aren't producing side effects without reading the code of the compiler itself?
Additionally you should know that functional programming is a lie. Your computer is an imperative machine with no understanding of functional programming. The compiler transforms your functional program into an imperative one.
Additionally you should know that functional programming is a lie. Your computer is an imperative machine with no understanding of functional programming
Yet you program a register machine as if it were a stack machine all the time without batting an eyelid!
>Because you can't make any guarantees about state in a language that wasn't intended for FP because how do you know what side effects the built-in functions are having
This is your original argument. I said that FP programs offer none of the said guarantees because they are at it's core compiled into imperative programs... You responded with a statement about a stack machine being an abstraction over a "register machine." How does the stack machine statement move your original argument forward...? We're getting side tracked here...
I'm very tempted to explore a coding style in C and C++ using a more functional idiom. I think both languages could benefit greatly if made more transparently 'intensional' -- more restricted use of in:out function arguments, explicit return variables, minimal pointer arithmetic, more explicit pointer expressions, etc.
Has anyone attempted to devise a FP-style guide for non-FP languages? It could be fun to reimagine their now-antiquated idioms spoken in a more intuitive and/or legible accent.
Just make every variable immutable. That is the only style guide you need to make the program part of the fp paradigm. The rest of the "functional patterns" flow naturally out of this restriction.
If the standard data structures in your language are mutable this will not save you. Luckily many languages like Java have nice third party persistent collection libraries
> People say they're doing FP in JavaScript. What they mean is they sprinkle reduce and map around and they use some pure functions. There's a lot of value in that. But otherwise their code is procedural. They have not learned the paradigm, only the features.
Yeah, but that's probably okay. I feel like there's a strong implication here that following the paradigm has inherent value but I'm not sure why I should think that's the case.
Basically, I agree with the claim above that "there's a lot of value in that." :)
I disagree with you. Map and reduce achieve the same result as a for loop so why not use a for loop? The end result is the same it's just a bit cooler or convenient to use map in place of a for loop, that's the only reason why you would use one instead of the other in a imperative program.
The functional paradigm fundamentally alters the way the entire program is constructed, and you can do it without map reduce or filter. You really need to play with haskell or lisp to see the light.
The result (return value) of a map is the list of results. A for loop has no result. So building up generic stream operators ((reduce (filter (map ...))) can't be done using for loops. It needs higher order functions or iterators.
Additionally the for construct implies that you want something done in a certain order, map implies all operations are independent and the order can be decided by the runtime itself. A program written in a language supporting map (which requires first class functions) can be trivially parallelised, whereas every for loop must be carefully analysed first.
Then replace the for loop with a parallel construct that's imperative. In terms of the language itself, map, reduce and filter are just sugar... different ways to loop through collections. Using one does not mean you are using FP, using immutability in java means that you are. That is the difference.
I don't. My point is, it's all sugar, so in a sense it's the same thing when you're doing imperative programming. Whether you use a map or a for loop in your imperative code the structure of your program remains the same, the only difference is sugar... This is my point.
Why are maps and folds so prevalent in functional programming? Because immutability and imperativeness render the concept of a for loop to be non-existent.
Try to use a for loop with all const variables and no IO... your for loop will not be able to do any meaningful change to the state of your program.
Obviously the for loop either transforms a list, or builds up a new list via an accumulator. That accumulator or the original list is your return value that you can imperatively pipe into other for loops.
You realize that reduce, filter and map are all higher order functions that can be implemented with for loops?
Yes because for loops are syntax sugar around gotos. It all boils down to the same thing. However maps can be determined to be turing incomplete if the mapped function has no function calls and no loops and if the input list is not infinite. This means that it's suitable for a wide range of dsls that would like to know if programs are susceptible to the halting problem (e.g. bpf -which doesnt have maps but I think it could...)
You just said a for loop returns no results. I responded saying that it can via an accumulator or mutating the original list...
Are you indicating in your latest response that I am correct and your original statement is incorrect? You seem to be going in on a tangent... Where is this going?
Returning a result and modifying a data structure you've decided to use as an accumulator are two different things. Modifying the original structure is even more different.
Most of the traditionally non-functional languages don't support loops as expressions.
Yes, I get what your saying, but I can implement the map filter and reduce abstractions with a for loop using this accumulator pattern or
pass in the parameter by value (aka copy) then modify the original structure. If I can implement MAP using a FOR loop then they are relatively the same thing as I can just replace a MAP with it's FOR loop definition and get the same result.
Here's my main point. There is no meaningful change to your imperative program when you replace for loops with maps. The core structure of your code is exactly the same. What you have introduced is a convenience aka sugar.
If you were to truly do functional programming the architecture of your entire program will be drastically different from imperative code... To counter the posters original statement: There is a gigantic difference between just using map and reduce in your imperative javascript code vs. actually writing a functional program... It is not a trivial difference.
I feel many people who understand javascript fp libraries like underscore think they know functional programming when all their really doing is sprinkling map and reduce all over their imperative code. You guys don't get it yet, and you'll never get it if you keep coding in javascript. The difference is night and day, it's like SQL vs python.
> Map and reduce achieve the same result as a for loop so why not use a for loop?
Map and reduce are more clear as to intent for the subset of what a for loop does that they, together, do, and that clarity and limitation has practical advantages for things like parallelization and distribution, which is why MapReduce is an important distributed computation model and ForLoop isn't.
> The functional paradigm fundamentally alters the way the entire program is constructed
Programming paradigms are useful at levels other than “entire program”, which is the reason many modern languages are multiparadigm.
Your first statement is correct but it's diverging away from my main point.
>Programming paradigms are useful at levels other than “entire program”, which is the reason many modern languages are multiparadigm.
Again I agree with this but your missing the point. To be a multiparadigm language the language needs to provide syntax for switching between muteability and immuteability. The original poster is not talking about this, he is talking about higher order functions which is an entirely different beast.
I would even argue that map filter and reduce aren't even part of any paradigm: functional or imperative as all of these functions can be implemented both using recursion and a for loop... The for loop however is strictly an imperative programming concept.
> Map and reduce achieve the same result as a for loop so why not use a for loop?
For one thing, because it's more work to convince ourselves that a loop is correct, than that a couple of canned list processing functions are used correctly.
So if the implementation of a HO function is a for loop then then an HO function and a for loop are equivalent. Thus proving my original point: It's the same thing. Using HO functions in an imperative language is not much different from using a for loop, it's all sugar.
Is that news to anyone? Sussman and Steele showed that tail recursive functions are equivalent to for loops over 40 years ago. Map, reduce, et al can be built on top of either of them, and they're just as useful built on top of either. They're factoring out common patterns, the same way printf, strlen, and memcpy do.
Apparently this concept is not even believed by the majority of people on this thread if you read the whole thing.
I originally stated that for loops and HO functions are equivalent and this entire thread consists of people disputing that statement. You're the one dude telling me that what I'm saying is old news and totally obvious. I'm not sure if you realize it, but we're on the same side.
As a side note, the equivalency between recursion and for loops is not limited to tail recursion. Recursion itself in all computing languages is implemented using a stack. So all recursion is equivalent to a for loop + a stack. This has been long known ever since programming languages utilized something called a call stack.
> Apparently this concept is not even believed by the majority of people on this thread if you read the whole thing.
> I originally stated that for loops and HO functions are equivalent and this entire thread consists of people disputing that statement.
My read of the thread is that your posts seem to be going beyond saying they're functionally equivalent, and saying that there's no value in using reduce and friends because they're functionally equivalent.
Most of your posts aren't addressing that tail recursion is a form of iteration (yes, or alternately that recursion can be done without a lexically recursive function) and that map/reduce/etc can be implemented in terms of recursion or for loops; you're contrasting the HOF's with for loops like they're competitors. The HOF's are an abstraction over iteration, whatever syntax was used to write that iteration.
Most of the responses aren't disputing that they accomplish the same thing, they're just saying that there is value in using the HOF's. You would be getting the same kinds of replies if you were insisting there's no difference between HOF's and direct recursion.
I quote myself:
> it's just a bit cooler or convenient to use map in place of a for
>Most of your posts aren't addressing that tail recursion is a form of iteration (yes, or alternately that recursion can be done without a lexically recursive function)
Why should I address this? This is not the main point. Even recursion without a tail can be considered a form of iteration. But how is this the topic of conversation? We are talking about the equivalency between HOFs and loops. Why are you bringing up the fixed point combinator?
>you're contrasting the HOF's with for loops like they're competitors. The HOF's are an abstraction over iteration, whatever syntax was used to write that iteration.
No I'm not! Not at all! I'm saying HOFs and LOOPS are ultimately the same thing!!! and thus when you use them in code you are not ultimately changing the paradigm of your programming to functional. The overall structure of your program is still imperative.
>You would be getting the same kinds of replies if you were insisting there's no difference between HOF's and direct recursion.
There's not much of a difference, I quote again:
>> it's just a bit cooler or convenient to use map in place of ...
> Why are you bringing up the fixed point combinator?
I didn't mean the fixed point combinator, I was responding to "So all recursion is equivalent to a for loop + a stack." A recursive algorithm implemented with a for loop and a stack instead of function calls and the processor stack isn't equivalent to recursion, it is recursion, just not the lexical kind. This is just semantics and we agree with each other.
> Why should I address this? We are talking about the equivalency between HOFs and
loops.
Because for loops are equivalent to recursive procedures, not to map and reduce; map and reduce are much more restricted.
You can implement a for loop using pure function application, and you can implement recursive pure functions using a for loop. Map and reduce live on a higher abstraction level, and because the two lower level strategies are equivalent, which one is used is irrelevant. Saying that they're not functional because they can be implemented with a for loop makes as much sense as saying that a for loop is functional because it can be implemented with pure function application.
To me, a for loop is an imperative construct, and map and reduce are functional constructs, regardless of how any of them are implemented.
>To me, a for loop is an imperative construct, and map and reduce are functional constructs, regardless of how any of them are implemented.
Well if the map is implemented using muteable variables then it is not a functional construct is it? If your entire program utilizes maps and filters and folds but is muteable then it is not a functional construct. Here is the definition of a functional language according to Wikipedia:
"In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. It is a declarative programming paradigm, which means programming is done with expressions[1] or declarations[2] instead of statements."
This article is describing something that is very true but in the end it doesn't teach you how to do FP in an otherwise imperative language. This is surprising as it's just one single devastatingly simple rule you need to follow in order to do functional programming:
After you declare and assign a value to a variable NEVER change it again. That's it. Immutability. Almost every other functional programming pattern flows naturally from this restriction.
People already know the definition of functional programming and that is a functional program is a program that consists of a single expression and that the complexity of this single expression arises from the fact that this expression is the composition of other smaller functions...
What they don't know is that if you take an imperative program and make every variable immutable and construct your program following this restriction the final result will be identical to a functional program! The two concepts are isomorphic!
54 comments
[ 3.0 ms ] story [ 119 ms ] threadSee? Easy to write :)
Keep in mind that passing a first class function into another function as a parameter is not that far off from passing the result of that function as a parameter.
Without first class functions an immutable program can still be turing complete. I would say that if a language only supports recursion and is immuteable, then that is all you need for the language to be part of the fp paradigm.
I'm sorry to say that if you don't understand this, you haven't really understood what functional programming is... You're just a guy who understands higher order functions.
...
> I'm sorry to say that if you don't understand this, you haven't really understood what functional programming is...
you can't be serious can you ?
>The only technical requirement for you to follow the functional paradigm is immutability.
Then you don't understand functional programming. I can't take you seriously if you claim otherwise.
Obviously, you highly disagree with me. Feel free to elaborate rather than waste my time with obviously rhetorical questions.
So are you saying that for instance both CaML and LISP aren't FP ? Because both are certainly not about immutability and you can write mutable messes in either.
Read the first line:
"In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. It is a declarative programming paradigm, which means programming is done with expressions[1] or declarations[2] instead of statements."
Key phrase: "avoids changing-state and mutable data."
You can use C++ as if it was a functional language just like you can use LISP and CaML as if variables were mutable. However in both cases you are bending the language to follow a paradigm that is NOT functional.
Not that far off unless you want to do partial application, currying, lazy evaluation, analyze, or change the code of the function before actually using it.
But that's not the point; a functional style can be achieved in any language as long as it has functions.
Additionally you should know that functional programming is a lie. Your computer is an imperative machine with no understanding of functional programming. The compiler transforms your functional program into an imperative one.
Yet you program a register machine as if it were a stack machine all the time without batting an eyelid!
This is your original argument. I said that FP programs offer none of the said guarantees because they are at it's core compiled into imperative programs... You responded with a statement about a stack machine being an abstraction over a "register machine." How does the stack machine statement move your original argument forward...? We're getting side tracked here...
Has anyone attempted to devise a FP-style guide for non-FP languages? It could be fun to reimagine their now-antiquated idioms spoken in a more intuitive and/or legible accent.
Yeah, but that's probably okay. I feel like there's a strong implication here that following the paradigm has inherent value but I'm not sure why I should think that's the case.
Basically, I agree with the claim above that "there's a lot of value in that." :)
The functional paradigm fundamentally alters the way the entire program is constructed, and you can do it without map reduce or filter. You really need to play with haskell or lisp to see the light.
Also, why would you prefer an imperative construct over different kinds of folds?
Why are maps and folds so prevalent in functional programming? Because immutability and imperativeness render the concept of a for loop to be non-existent.
Try to use a for loop with all const variables and no IO... your for loop will not be able to do any meaningful change to the state of your program.
You realize that reduce, filter and map are all higher order functions that can be implemented with for loops?
Are you indicating in your latest response that I am correct and your original statement is incorrect? You seem to be going in on a tangent... Where is this going?
Most of the traditionally non-functional languages don't support loops as expressions.
Here's my main point. There is no meaningful change to your imperative program when you replace for loops with maps. The core structure of your code is exactly the same. What you have introduced is a convenience aka sugar.
If you were to truly do functional programming the architecture of your entire program will be drastically different from imperative code... To counter the posters original statement: There is a gigantic difference between just using map and reduce in your imperative javascript code vs. actually writing a functional program... It is not a trivial difference.
I feel many people who understand javascript fp libraries like underscore think they know functional programming when all their really doing is sprinkling map and reduce all over their imperative code. You guys don't get it yet, and you'll never get it if you keep coding in javascript. The difference is night and day, it's like SQL vs python.
Map and reduce are more clear as to intent for the subset of what a for loop does that they, together, do, and that clarity and limitation has practical advantages for things like parallelization and distribution, which is why MapReduce is an important distributed computation model and ForLoop isn't.
> The functional paradigm fundamentally alters the way the entire program is constructed
Programming paradigms are useful at levels other than “entire program”, which is the reason many modern languages are multiparadigm.
>Programming paradigms are useful at levels other than “entire program”, which is the reason many modern languages are multiparadigm.
Again I agree with this but your missing the point. To be a multiparadigm language the language needs to provide syntax for switching between muteability and immuteability. The original poster is not talking about this, he is talking about higher order functions which is an entirely different beast.
I would even argue that map filter and reduce aren't even part of any paradigm: functional or imperative as all of these functions can be implemented both using recursion and a for loop... The for loop however is strictly an imperative programming concept.
and how many of these "parallelized and distributed" map and reduces actually exist out in the wilderness of javascript code ?
For one thing, because it's more work to convince ourselves that a loop is correct, than that a couple of canned list processing functions are used correctly.
So? They abstract out common patterns. You could write the great majority of functions' implementations inline instead of calling them.
I originally stated that for loops and HO functions are equivalent and this entire thread consists of people disputing that statement. You're the one dude telling me that what I'm saying is old news and totally obvious. I'm not sure if you realize it, but we're on the same side.
As a side note, the equivalency between recursion and for loops is not limited to tail recursion. Recursion itself in all computing languages is implemented using a stack. So all recursion is equivalent to a for loop + a stack. This has been long known ever since programming languages utilized something called a call stack.
> I originally stated that for loops and HO functions are equivalent and this entire thread consists of people disputing that statement.
My read of the thread is that your posts seem to be going beyond saying they're functionally equivalent, and saying that there's no value in using reduce and friends because they're functionally equivalent.
Most of your posts aren't addressing that tail recursion is a form of iteration (yes, or alternately that recursion can be done without a lexically recursive function) and that map/reduce/etc can be implemented in terms of recursion or for loops; you're contrasting the HOF's with for loops like they're competitors. The HOF's are an abstraction over iteration, whatever syntax was used to write that iteration.
Most of the responses aren't disputing that they accomplish the same thing, they're just saying that there is value in using the HOF's. You would be getting the same kinds of replies if you were insisting there's no difference between HOF's and direct recursion.
> You're the one dude
I'm not a dude.
I quote myself: > it's just a bit cooler or convenient to use map in place of a for
>Most of your posts aren't addressing that tail recursion is a form of iteration (yes, or alternately that recursion can be done without a lexically recursive function)
Why should I address this? This is not the main point. Even recursion without a tail can be considered a form of iteration. But how is this the topic of conversation? We are talking about the equivalency between HOFs and loops. Why are you bringing up the fixed point combinator?
>you're contrasting the HOF's with for loops like they're competitors. The HOF's are an abstraction over iteration, whatever syntax was used to write that iteration.
No I'm not! Not at all! I'm saying HOFs and LOOPS are ultimately the same thing!!! and thus when you use them in code you are not ultimately changing the paradigm of your programming to functional. The overall structure of your program is still imperative.
>You would be getting the same kinds of replies if you were insisting there's no difference between HOF's and direct recursion.
There's not much of a difference, I quote again: >> it's just a bit cooler or convenient to use map in place of ...
I didn't mean the fixed point combinator, I was responding to "So all recursion is equivalent to a for loop + a stack." A recursive algorithm implemented with a for loop and a stack instead of function calls and the processor stack isn't equivalent to recursion, it is recursion, just not the lexical kind. This is just semantics and we agree with each other.
> Why should I address this? We are talking about the equivalency between HOFs and loops.
Because for loops are equivalent to recursive procedures, not to map and reduce; map and reduce are much more restricted.
You can implement a for loop using pure function application, and you can implement recursive pure functions using a for loop. Map and reduce live on a higher abstraction level, and because the two lower level strategies are equivalent, which one is used is irrelevant. Saying that they're not functional because they can be implemented with a for loop makes as much sense as saying that a for loop is functional because it can be implemented with pure function application.
To me, a for loop is an imperative construct, and map and reduce are functional constructs, regardless of how any of them are implemented.
Well if the map is implemented using muteable variables then it is not a functional construct is it? If your entire program utilizes maps and filters and folds but is muteable then it is not a functional construct. Here is the definition of a functional language according to Wikipedia:
"In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. It is a declarative programming paradigm, which means programming is done with expressions[1] or declarations[2] instead of statements."
After you declare and assign a value to a variable NEVER change it again. That's it. Immutability. Almost every other functional programming pattern flows naturally from this restriction.
People already know the definition of functional programming and that is a functional program is a program that consists of a single expression and that the complexity of this single expression arises from the fact that this expression is the composition of other smaller functions...
What they don't know is that if you take an imperative program and make every variable immutable and construct your program following this restriction the final result will be identical to a functional program! The two concepts are isomorphic!
Try it if you don't believe me.
I should hope you can do floating point math in just about any language.
Yeesh.
;)