Functional programming and non-functional programming [closed]

Question

In my second year of University we were "taught" Haskell, I know almost nothing about it and even less about functional programming.

What is functional programming, why and/xor where would I want to use it instead of non-functional programming and am I correct in thinking that C is a non-functional programming language?

Stacte

Answer 1

One key feature in a functional language is the concept of first-class functions. The idea is that you can pass functions as parameters to other functions and return them as values.

Functional programming involves writing code that does not change state. The primary reason for doing so is so that successive calls to a function will yield the same result. You can write functional code in any language that supports first-class functions, but there are some languages, like Haskell, which do not allow you to change state. In fact, you're not supposed to make any side effects (like printing out text) at all - which sounds like it could be completely useless.

Haskell instead employs a different approach to IO: monads. These are objects that contain the desired IO operation to be executed by your interpreter's toplevel. At any other level they are simply objects in the system.

What advantages does functional programming provide? Functional programming allows coding with fewer potentials for bugs because each component is completely isolated. Also, using recursion and first-class functions allows for simple proofs of correctness which typically mirror the structure of the code.

Midst

"The primary reason for doing so is so that successive calls to a function will yield the same result" Why do we want successive calls to a function to yield the same result. What is the problem with the way things are in C? I never understood this. – Lauralee

@Lauralee There are a few reasons why that's undesirable. First, if a function returns the same result, then you can cache that result and return it if the function is called again. Second, if the function does not return the same result, that means that it's relying on some external state of the program, and as such the function can't be easily precomputed or parallelized. – Midst

Also it is a huge benefit when analyzing and debugging code. Side effects are basically just implicit input to the function hidden from the programmer. – Cockhorse

@MagnusKronqvist if they are mutable, they are not same as implicit inputs, because they can be written to. Input arguments normally can't be written to (unless they are reference type). The importance of the distinction is that accessing mutable external state, makes the function imperative and not declarative. – Acetometer

"You can write functional code in any language that supports first-class functions" - I would add that 1) having typeclass support in the language saves you from lots of repetition, and 2) Java can also represent first class functions (with single-method class objects, see Guava's Function of FunctionalJava's F), but the syntax is too verbose to be consumable. – Perkin

Answer 2

What is functional programming

There are two different definitions of "functional programming" in common use today:

The older definition (originating from Lisp) is that functional programming is about programming using first-class functions, i.e. where functions are treated like any other value so you can pass functions as arguments to other functions and function can return functions among their return values. This culminates in the use of higher-order functions such as map and reduce (you may have heard of mapReduce as a single operation used heavily by Google and, unsurprisingly, it is a close relative!). The .NET types System.Func and System.Action make higher-order functions available in C#. Although currying is impractical in C#, functions that accept other functions as arguments are common, e.g. the Parallel.For function.

The younger definition (popularized by Haskell) is that functional programming is also about minimizing and controlling side effects including mutation, i.e. writing programs that solve problems by composing expressions. This is more commonly called "purely functional programming". This is made possible by wildly different approaches to data structures called "purely functional data structures". One problem is that translating traditional imperative algorithms to use purely functional data structures typically makes performance 10x worse. Haskell is the only surviving purely functional programming language but the concepts have crept into mainstream programming with libraries like Linq on .NET.

where would I want to use it instead of non-functional programming

Everywhere. Lambdas in C# have now demonstrated major benefits. C++11 has lambdas. There's no excuse not to use higher-order functions now. If you can use a language like F# you'll also benefit from type inference, automatic generalization, currying and partial application (as well as lots of other language features!).

am I correct in thinking that C is a non-functional programming language?

Yes. C is a procedural language. However, you can get some of the benefit of functional programming by using function pointers and void * in C.

Pleonasm

Can you please elaborate more on this line, or share an example : "One problem is that translating traditional imperative algorithms to use purely functional data structures typically makes performance 10x worse." – Mealie

Almost all traditional algorithms (e.g. quicksort, LZW, LU decomposition, Prim's MST) are almost always inherently imperative in nature. Specifically, they never stand to benefit from persistence: they always operate only on the latest version of a collection and never reuse old versions. This makes them ideal for implementation using traditional mutable collections but it means that if you implement them using purely functional collections then you pay the price for persistence (i.e. slow speed) but reap no benefits. – Pleonasm

Instead you must look more carefully for exotic algorithms that solve the same problem and do stand to benefit from persistence, such as merge sort and Borůvka's MST. – Pleonasm

Answer 3

May be worth checking out this article on F# "101" on CoDe Mag recently posted.

Also, Dustin Campbell has a great blog where he has posted many articles on his adventures on getting up to speed with F#..

I hope you find these useful :)

EDIT:

Also, just to add, my understanding of functional programming is that everything is a function, or parameters to a function, rather than instances/stateful objects.. But I could be wrong F# is something I am dying to get in to but just dont have the time! :)

Indorse

Answer 4

John the Statistician's example code does not show functional programming, because when you're doing functional programming, the key is that the code does NO ASSIGNMENTS ( record = thingConstructor(t) is an assignment), and it has NO SIDE EFFECTS (localMap.put(record) is a statement with a side effect). As a result of these two constraints, everything that a function does is fully captured by its arguments and its return value. Rewriting the Statistician's code the way it would have to look, if you wanted to emulate a functional language using C++:

RT getOrCreate(const T thing, 
                  const Function<RT<T>> thingConstructor, 
                  const Map<T,RT<T>> localMap) {
    return localMap.contains(t) ?
        localMap.get(t) :
        localMap.put(t,thingConstructor(t));
}

As a result of the no side-effects rule, every statement is part of the return value (hence return comes first), and every statement is an expression. In languages that enforce functional programming, the return keyword is implied, and the if statement behaves like C++'s ?: operator.

Also, everything is immutable, so localMap.put has to create a new copy of localMap and return it, instead of modifying the original localMap, the way a normal C++ or Java program would. Depending on the structure of localMap, the copy could re-use pointers into the original, reducing the amount of data that has to be copied.

Some of the advantages of functional programming include the fact that functional programs are shorter, and it is easier to modify a functional program (because there are no hidden global effects to take into account), and it is easier to get the program right in the first place.

However, functional programs tend to run slowly (because of all the copying they have to do), and they don't tend to interact well with other programs, operating system processes, or operating systems, which deal in memory addresses, little-endian blocks of bytes, and other machine-specific, non-functional bits. The degree of noninteroperability tends to be inversely correlated with the degree of functional purity, and the strictness of the type system.

The more popular functional languages have really, really strict type systems. In OCAML, you can't even mix integer and floating-point math, or use the same operators (+ is for adding integers, +. is for adding floats). This can be either an advantage or a disadvantage, depending on how highly you value the ability of a type checker to catch certain kinds of bugs.

Functional languages also tend to have really big runtime environments. Haskell is an exception (GHC executables are almost as small as C programs, both at compile-time and runtime), but SML, Common Lisp, and Scheme programs always require tons of memory.

Crabber

I disagree, in that functional languages can (and, like Erlang, occasionally do) allow single assignments, which don't have side effects. However, your point about side-effects is well-taken. I am not going to change my code, though, since I think illustrating the advantage of functional features in a hybrid language is more important than a strict purity. – Acidulent

The vast majority of functional programming is about the use of first-class functions and not about the prohibition of side effects. My measurements indicate that your statements about the sizes of run-time environments are wrong: GHC produces binaries twice the size of OCaml and Standard ML (using MLton) and 20× the size of HLVM. – Pleonasm

Don't conflate FP with side-effect free, i.e. with DP vs. IP. That is pure FP. – Acetometer

Answer 5

Yes you are correct in thinking that C is a non-functional language. C is a procedural language.

Dallapiccola

Answer 6

I prefer to use functional programming to save myself repeated work, by making a more abstract version and then using that instead. Let me give an example. In Java, I often find myself creating maps to record structures, and thus writing getOrCreate structures.

SomeKindOfRecord<T> getOrCreate(T thing) { 
    if(localMap.contains(thing)) { return localMap.get(thing); }
    SomeKindOfRecord<T> record = new SomeKindOfRecord<T>(thing);
    localMap = localMap.put(thing, record);
    return record; 
}

This happens very often. Now, in a functional language I could write

RT<T> getOrCreate(T thing, 
                  Function<RT<T>> thingConstructor, 
                  Map<T,RT<T>> localMap) {
    if(localMap.contains(thing)) { return localMap.get(thing); }
    RT<T> record = thingConstructor(thing);
    localMap = localMap.put(thing,record);
    return record; 
}

and I would never have to write a new one of these again, I could inherit it. But I could do one better than inheriting, I could say in the constructor of this thing

getOrCreate = myLib.getOrCreate(*,
                                SomeKindOfRecord<T>.constructor(<T>), 
                                localMap);

(where * is a kind of "leave this parameter open" notation, which is a sort of currying)

and then the local getOrCreate is exactly the same as it would have been if I wrote out the whole thing, in one line, with no inheritance dependencies.

Acidulent

Answer 7

If you are looking for a good text on F#

Expert F# is co-written by Don Syme. Creator of F#. He worked on generics in .NET specifically so he could create F#.

F# is modeled after OCaml so any OCaml text would help you learn F# as well.

Aggi

Did Don really just do generics for F#? I find that suspiciously surprising! – Pleonasm

Answer 8

I find What Is Functional Programming? to be useful

Functional programming is about writing pure functions, about removing hidden inputs and outputs as far as we can, so that as much of our code as possible just describes a relationship between inputs and outputs.

Prefer explicit when param

public Program getProgramAt(TVGuide guide, int channel, Date when) {
  Schedule schedule = guide.getSchedule(channel);

  Program program = schedule.programAt(when);

  return program;
}

over

public Program getCurrentProgram(TVGuide guide, int channel) {
  Schedule schedule = guide.getSchedule(channel);

  Program current = schedule.programAt(new Date());

  return current;
}

A functional language is actively hostile to side-effects. Side-effects are complexity and complexity is bugs and bugs are the devil. A functional language will help you be hostile to side-effects too.

Helvetian