How is functional programming useful

[BigBear]

So I been reading about Falcon and got to the section about functional programming and I am wondering how is functional programming useful.

Can you make obtain the same result from a procedural program?

Can someone show me the same program in both.

Is functional programming an important part to a programming language?

Falcon does both so it works for everyone to bad it is just a scripting language .

[Prabhakar Ragde]

BigBear @ Sun May 09, 2010 10:43 am wrote:

So I been reading about Falcon and got to the section about functional programming and I am wondering how is functional programming useful.

Many CS concepts are more clearly and elegantly expressed using the functional paradigm.

Quote:

Can you make obtain the same result from a procedural program?

A general-purpose functional programming language can compute anything that an imperative language can, and vice-versa. The computation may be expressed in a different fashion.

Quote:

Can someone show me the same program in both.

The Wikipedia article on "functional programming" is a reasonable place to start. It has only one small example, but you can find others if you look at articles on major functional programming languages such as Lisp, Scheme, ML, Haskell, and Erlang.

Quote:

Is functional programming an important part to a programming language?

It is often useful, which is why it shows up in many scripting and "multi-paradigm" languages, and why some features of functional programming languages are being added to imperative languages such as C++ and C#. Its importance depends on how well it is supported within a language.

[Tony]

Some concepts are much easier to express with functional syntax. It's in your best interest to have experience with multiple programming paradigms; then you can pick the best one for any particular task.

BigBear @ Sun May 09, 2010 10:43 am wrote:

to bad it is just a scripting language .

By "scripting", do you mean "interpreted"? E.g. Java (byte-code on JVM) and C# (CIL on .Net).

What kind of tools would you prefer instead, and why?

[DtY]

Are use the example of python, since it does imperative and functional programming both well.

Say I have a list of numbers, I want to make new lists that will have the squares of these numbers, another that has all the cubes, another that has all the numbers that are even, and a last that is only odds.

Python:

#Imperitive numbers = range(100) #Square all the numbers squares = [ ] for a in numbers:     squares.append(a*a) #Cubes cubes = [ ] for a in numbers:     squares.append(a*a*a) #Even numbers evens = [ ] for a in numbers:     if a&1:         evens.append(a) #Odd numbers odds = [ ] for a in numbers:     if not a&1:         odds.append(a) #Granted, all these could be combined into a single loop #if they were right next to each other like these are #Same thing, but functional def map(func, seq):     #There is a built in function named map() that does     #this, but I will rewrite it for demonstration     out = [ ]     for a in seq:         out.append(func(a))     return out def filter(func, seq):     #As with map(), filter() already is builtin     out = [ ]     for a in seq:         if func(a):             out.append(a) numbers = range(100) squares = map(lambda n: n*n, numbers) cubes = map(lambda n: n*n*n, numbers) evens = map(lambda n: n&1, numbers) odds = map(lambda n: not n&1, numbers)

Some functional languages (for example, Haskell) use pure functions, which means that with the same input, the function will always give the same output, which allows the code to be greatly optimized, especially with tree recursion,

Python:

def fib(n):     if n==1 or n==2: return 1     else: return fib(n-1) + fin(n-2)

Give this a big number and it will take ages to compute. Why? The same Fibonacci number is requested many many times. But, fib(5) will always be five, there's no need to compute it over and over. Because of this knowledge, Haskell would only compute each Fibonacci number once, and remember that.

[Prabhakar Ragde]

DtY @ Sun May 09, 2010 6:15 pm wrote:

Some functional languages (for example, Haskell) use pure functions, which means that with the same input, the function will always give the same output, which allows the code to be greatly optimized, especially with tree recursion,

Python:

def fib(n):     if n==1 or n==2: return 1     else: return fib(n-1) + fin(n-2)

Give this a big number and it will take ages to compute. Why? The same Fibonacci number is requested many many times. But, fib(5) will always be five, there's no need to compute it over and over. Because of this knowledge, Haskell would only compute each Fibonacci number once, and remember that.

Actually, this is not quite accurate. If you write the equivalent Haskell function:

Haskell:

fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)

and evaluate "fib 1000", it will take a very long time (albeit less time than the Python program). Haskell does not memoize function values. You can do this yourself, for instance by storing the values in a list. In fact, you can define the infinite list of all Fibonacci numbers as follows:

Haskell:

fibs = 0:1: zipWith (+) fibs (tail fibs)

Now evaluating "fibs !! 1000" will give you an answer relatively quickly.

[BigBear]

Tony @ Sun May 09, 2010 3:03 pm wrote:

BigBear @ Sun May 09, 2010 10:43 am wrote:

to bad it is just a scripting language .

By "scripting", do you mean "interpreted"? E.g. Java (byte-code on JVM) and C# (CIL on .Net).

What kind of tools would you prefer instead, and why?

Falcon programming FAQ wrote:

Our aim is to make Falcon the ultimate scripting language, including the ability to create mid-sized applications. As such, Falcon aims to be good on what scripting languages should be good:

Integration with the surrounding environment (libraries, servers, systems).
Abstraction of the underlying system / cross-platform / international development.
Text manipulation.
(non-statistical) data analysis.
System maintenance.
File dumping.
Embedding into application (for real-time data control/flexible manipulation).
Application of high level logic to computing problems.
What Falcon is not aimed to do is usually what we explicitly leave to "all muscle" and "domain specific" languages:

Massive computational intensive tasks (i.e. matrix algebra, pure statistical analysis, arbitrary precision math).
Pure 2D/3D Graphics elaboration (i.e. rendering).
Database.

It is mainly for scripting for other applications (Embedding into application) at least that is what I take from it. It does not have a graphics API as far as I know, if anyone knows one let me know.

I don't really have a main programming language atm, I am learning C++ in school and I just started learning SDL, so I guess it is C++.

Falcon is amazingly simply, double clicking the source compiles it and the lack of setup is nice. Maybe that is because I have not used an external library. Or had to install each package the same way and have a bunch of dll files like SDL.

[DtY]

Prabhakar Ragde @ Sun May 09, 2010 8:31 pm wrote:

DtY @ Sun May 09, 2010 6:15 pm wrote:

Some functional languages (for example, Haskell) use pure functions, which means that with the same input, the function will always give the same output, which allows the code to be greatly optimized, especially with tree recursion,

Python:

def fib(n):     if n==1 or n==2: return 1     else: return fib(n-1) + fin(n-2)

Give this a big number and it will take ages to compute. Why? The same Fibonacci number is requested many many times. But, fib(5) will always be five, there's no need to compute it over and over. Because of this knowledge, Haskell would only compute each Fibonacci number once, and remember that.

Actually, this is not quite accurate. If you write the equivalent Haskell function:

Haskell:

fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)

and evaluate "fib 1000", it will take a very long time (albeit less time than the Python program). Haskell does not memoize function values. You can do this yourself, for instance by storing the values in a list. In fact, you can define the infinite list of all Fibonacci numbers as follows:

Haskell:

fibs = 0:1: zipWith (+) fibs (tail fibs)

Now evaluating "fibs !! 1000" will give you an answer relatively quickly.

Interesting, I just did some searches about this, because I was sure that Haskell does memoize all functions, but it appears that the standard does not require results to be memoized, but that the compiler can if it chooses. I was also sure that GHC memoized the Fibonacci function last time I wrote it, but I went back and gave it a try, and it appeared not to (fib 31 was slow after evaluating fib 31).

[chrisbrown]

Prabhakar Ragde @ Sun May 09, 2010 8:31 pm wrote:

albeit less time than the Python program

Out of curiosity, can I ask why?

[Tony]

Also

Haskell:

fib n = round $ phi ** fromIntegral n / sq5   where     sq5 = sqrt 5 >:: Double     phi = (1 + sq5) / 2

http://www.haskell.org/haskellwiki/The_Fibonacci_sequence#Constant-time_implementations


wooo, Math!

[Prabhakar Ragde]

DtY: Since Haskell is pure, it won't change the result if the compiler memoizes functions, but in some cases this slows down the computation, so it is typically left to the programmer to decide.

methodoxx: It's not inherent in the languages, but GHCi tends to be faster than CPython. The purity of Haskell allows GHC to do some pretty good optimizing. In this case, we are talking about a constant factor on top of an exponentially slow computation that no one should perform as anything but a bad example, so it's not really relevant.

Tony: That's an approximation, not an exact computation [though it can be made exact by representing a + b sqrt 5 as the pair (a,b)]. The "logarithmic time" computations a little higher up on that page are exact (the Haskell type Int is a 32-bit integer, but Integer is unbounded). They are not actually logarithmic time, because that analysis neglects the time needed to perform arithmetic on numbers of unbounded precision. Exercise: what is the time needed to compute F_n, as a function of n, using one of these techniques?

[jcollins1991]

I'm surprised no one has mentioned Scheme in this thread, probably just my university forced us to take it in our first programming course... At first I thought it was crazy, but now that we're working in C I'm beginning to miss it... I agree with Prabhakar when he says that functional programming languages can be more elegant for certain CS concepts... I'm not sure about the efficiency when compared to implementations in functional languages, but in Scheme its extremely simple to implement various functions using lists, trees, etc... If you take quick sort as an example, a version of it in C code is long and might take a bit of reading to understand the implementation, but the code I just wrote in a minute in Scheme is (IMO) fairly easy to understand and just looking at it you can see how it relates to the general concept of quicksort...

code:

(define (quicksort lst)   (cond [(empty? lst) empty]         [else (append (quicksort (filter (lambda (x) (< x (first lst))) lst))                       (list (first lst))                       (quicksort (filter (lambda (x) (> x (first lst))) lst)))]))

Another thing I like about functional programming (or maybe just Scheme) is how fast you can make programs... I was bored today so in my friends CS lecture I wrote Scheme code for a puzzle (http://www.facebook.com/careers/puzzles.php?puzzle_id=6) and had a fully working program in under an hour... I know its a fairly simple problem that shouldn't take very long anyways, but if I had initially tried it in C I'd probably still be stuck on pointless errors trying to find out what part of my program messed around with memory it wasn't supposed to... In my Scheme code the only errors I had were because I was missing a variable in a function call or because I was passing a structure when I only wanted part of it, errors that are fairly easy to find and fix...

[Prabhakar Ragde]

jcollins1991 @ Thu May 13, 2010 11:07 pm wrote:

I'm surprised no one has mentioned Scheme in this thread, probably just my university forced us to take it in our first programming course...

Hey, I mentioned Scheme. But someone else posted a Haskell program. Haskell is more expressive and easier for read, but it's harder to program in for newcomers. Both UW and UBC (among Canadian universities) are using Scheme in a first course.

Quote:

I'm not sure about the efficiency when compared to implementations in functional languages, but in Scheme its extremely simple to implement various functions using lists, trees, etc...

This is what makes it good for education and for the kinds of things that scripting languages are used for. As for efficiency, PLT Scheme is designed for teaching, but it's reasonably fast for an interpreter (typically faster than CPython and Ruby). There are Scheme compilers available (e.g. Gambit, Chez Scheme) but Scheme, being dynamically typed, requires a certain amount of run-time overhead. Statically-typed functional languages such as Haskell and OCaML can be competitive with imperative languages while preserving the quality of being more expressive.

Quote:

If you take quick sort as an example, a version of it in C code is long and might take a bit of reading to understand the implementation, but the code I just wrote in a minute in Scheme is (IMO) fairly easy to understand and just looking at it you can see how it relates to the general concept of quicksort...

There is, however, a bug in your code. Can you figure out what it is?

Quote:

I know its a fairly simple problem that shouldn't take very long anyways, but if I had initially tried it in C I'd probably still be stuck on pointless errors trying to find out what part of my program messed around with memory it wasn't supposed to... In my Scheme code the only errors I had were because I was missing a variable in a function call or because I was passing a structure when I only wanted part of it, errors that are fairly easy to find and fix...

I've had students say to me, "It doesn't always work the first time... but it usually works the second time." I'm sure you're finding that testing in C is much more of a pain than it is in Scheme. In Scheme, you're typically writing functions without side effects, and every Scheme value has a printable form, so one test just constructs a value and applies a function to it, taking up one line of code. In C, you typically have to write a driver program, plus read and print routines for your data structure, plus a separate file for each input and one for each expected output, plus a shell script to run your program on each sample input and "diff" the result against the expected output. That's enough of a nuisance that everyone skimps on it... making it more likely that bugs persist.

[jcollins1991]

Prabhakar Ragde @ Fri May 14, 2010 7:38 am wrote:

Hey, I mentioned Scheme. But someone else posted a Haskell program. Haskell is more expressive and easier for read, but it's harder to program in for newcomers. Both UW and UBC (among Canadian universities) are using Scheme in a first course.

Ooops, I was half asleep when I was posting and completely forgot you'd mentioned it...

Prabhakar Ragde @ Fri May 14, 2010 7:38 am wrote:

There is, however, a bug in your code. Can you figure out what it is?

Yup, it doesn't account for duplicates of numbers in a list... I knew this when I posted but wasn't thinking and forgot to mention it, I think there's a way to get around that but I was half asleep so just posted what I had... I've rewritten it to function (hopefully) like the C code I had linked to by indexing the numbers in the list at the start... There's probably a much nicer way to fix my problem but I'm not sure what it'd be right now...

code:

(define (quicksort lst)   (unindex (sorter (indexer lst 0)))) (define (indexer lst n)   (cond [(empty? lst) empty]         [else (cons (list (first lst) n)                     (indexer (rest lst) (add1 n)))])) (define (sorter lst)   (cond [(empty? lst) empty]         [else (append (sorter (filter (lambda (x) (cond [(= (first x) (first (first lst)))                                                             (< (second x) (second (first lst)))]                                                            [else (< (first x) (first (first lst)))])) lst))                       (list (first lst))                       (sorter (filter (lambda (x) (cond [(= (first x) (first (first lst)))                                                             (> (second x) (second (first lst)))]                                                            [else (> (first x) (first (first lst)))])) lst)))])) (define (unindex lst)   (cond [(empty? lst) empty]         [else (cons (first (first lst))                     (unindex (rest lst)))]))

Prabhakar Ragde @ Fri May 14, 2010 7:38 am wrote:

I've had students say to me, "It doesn't always work the first time... but it usually works the second time." I'm sure you're finding that testing in C is much more of a pain than it is in Scheme. In Scheme, you're typically writing functions without side effects, and every Scheme value has a printable form, so one test just constructs a value and applies a function to it, taking up one line of code. In C, you typically have to write a driver program, plus read and print routines for your data structure, plus a separate file for each input and one for each expected output, plus a shell script to run your program on each sample input and "diff" the result against the expected output. That's enough of a nuisance that everyone skimps on it... making it more likely that bugs persist.

I think for me the only reason C is more annoying is because you don't think much about it ahead of time because there are so many little details you're not sure of before you actually start coding... For my final assignment last term I actually wrote out all of my C code by hand before writing it up and got just as few errors as I would have gotten if I had been coding in Scheme (all 5 variations of the scoreboard program from CS136 if you know what I'm talking about)... I realize this probably wouldn't translate that well to people who are writing extremely large programs, but I think writing out the programs and actually thinking about what they're doing instead of just staring at code is much more useful for finding your errors...

[Prabhakar Ragde]

jcollins1991 @ Fri May 14, 2010 9:50 am wrote:

I've rewritten it to function (hopefully) like the C code I had linked to by indexing the numbers in the list at the start... There's probably a much nicer way to fix my problem but I'm not sure what it'd be right now...

Um, don't do that. There is a simple edit to the last line of your original (much better) implementation that will take care of the error.

Quote:

For my final assignment last term I actually wrote out all of my C code by hand before writing it up and got just as few errors as I would have gotten if I had been coding in Scheme (all 5 variations of the scoreboard program from CS136 if you know what I'm talking about)... I realize this probably wouldn't translate that well to people who are writing extremely large programs, but I think writing out the programs and actually thinking about what they're doing instead of just staring at code is much more useful for finding your errors...

It was enlightened of you to do that. Most students would say, "Why waste time writing by hand when I can type?" and then "Now that I have the program typed in, let me just see if it compiles and runs, because if it does, that will save me thinking about it," and then, "Damn! It doesn't work! Maybe if I change this..." and they're on the treadmill and can't get off. But an ounce of prevention (thinking carefully) is worth a pound of cure (debugging).

Scaling up from small programs, you can design top-down and test bottom-up, but you have to be disciplined about it.

[Insectoid]

I'm really starting to get interested in functional programming. Maybe I'll download a scheme or haskell compiler/interpreter and try it out.