Computer Science Canada :: View topic - How is functional programming useful

Computer Science Canada

How is functional programming useful

Author:	BigBear [ Sun May 09, 2010 10:43 am ]
Post subject:	How is functional programming useful
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 .

Author:	Prabhakar Ragde [ Sun May 09, 2010 11:02 am ]
Post subject:	Re: How is functional programming useful
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.

Author:	Tony [ Sun May 09, 2010 3:03 pm ]
Post subject:	Re: How is functional programming useful
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?

Author:

DtY [ Sun May 09, 2010 6:15 pm ]

Post subject:

RE:How is functional programming useful

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.

Author:

Prabhakar Ragde [ Sun May 09, 2010 8:31 pm ]

Post subject:

Re: RE:How is functional programming useful

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

Python:

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

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.

Author:	BigBear [ Sun May 09, 2010 8:52 pm ]
Post subject:	Re: How is functional programming useful
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.

Author:

DtY [ Sun May 09, 2010 9:22 pm ]

Post subject:

Re: RE:How is functional programming useful

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

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

Python:

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

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)

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).

Author:	chrisbrown [ Sun May 09, 2010 9:46 pm ]
Post subject:	Re: RE:How is functional programming useful
Prabhakar Ragde @ Sun May 09, 2010 8:31 pm wrote: albeit less time than the Python program Out of curiosity, can I ask why?

Author:

Tony [ Mon May 10, 2010 1:16 am ]

Post subject:

Re: How is functional programming useful

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!

Author:	Prabhakar Ragde [ Mon May 10, 2010 9:43 am ]
Post subject:	RE:How is functional programming useful
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?

Author:

jcollins1991 [ Thu May 13, 2010 11:07 pm ]

Post subject:

Re: How is functional programming useful

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...

Author:	Prabhakar Ragde [ Fri May 14, 2010 7:38 am ]
Post subject:	Re: How is functional programming useful
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.

Author:

jcollins1991 [ Fri May 14, 2010 9:50 am ]

Post subject:

Re: How is functional programming useful

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...

Author:	Prabhakar Ragde [ Fri May 14, 2010 11:39 am ]
Post subject:	Re: How is functional programming useful
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.

Author:	Insectoid [ Fri May 14, 2010 12:22 pm ]
Post subject:	RE:How is functional programming useful
I'm really starting to get interested in functional programming. Maybe I'll download a scheme or haskell compiler/interpreter and try it out.

Author:	Prabhakar Ragde [ Fri May 14, 2010 12:41 pm ]
Post subject:	RE:How is functional programming useful
I would recommend downloading DrScheme and looking at the draft of HtDP/2e here: http://www.ccs.neu.edu/home/matthias/HtDP2e/ Haskell is very cool but you do need to understand a fair amount of theory to use it. The error messages can be brutal without the proper background. That said, the Haskell community is very active and there are some good tutorials and books. GHC is the way to go if you want to try it.

Author:

jcollins1991 [ Fri May 14, 2010 12:43 pm ]

Post subject:

Re: How is functional programming useful

Prabhakar Ragde @ Fri May 14, 2010 11:39 am wrote:

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.

code:

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

I knew the fix had something to do with adding an = but forgot the rest so just went to thinking about total order and ordered sets >__<...

Insectoid wrote:

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

If you want to learn Scheme you could go to the UW site or another universities site and read through some of their materials and assignments (I'm not sure if they like you doing that, but many of the course sites for university CS courses are publicly accessible), but since it's early in the term you probably won't find much yet... There's also a free copy of a Scheme textbook online (http://www.htdp.org/)... Just gonna also mention that the Dr. Scheme editor will do proper brackets for your code, which can be useful when you have a bunch of round and square closing brackets at the end... I don't know anything about Haskell so I can't help you there :S...

Author:	DtY [ Fri May 14, 2010 3:01 pm ]
Post subject:	Re: RE:How is functional programming useful
Insectoid @ Fri May 14, 2010 12:22 pm wrote: I'm really starting to get interested in functional programming. Maybe I'll download a scheme or haskell compiler/interpreter and try it out. Do you use a *nix? I liked MIT Scheme more than Dr. Scheme, but I don't know if there's a windows port of MIT scheme. I would suggest scheme over Haskell, functional languages (other that lisps) seem to always have way too much confusing syntax, Haskell included.

Author:	bbi5291 [ Fri May 14, 2010 3:28 pm ]
Post subject:	Re: How is functional programming useful
I found functional programming much more difficult to learn than imperative programming. It forces you to think in a more structured manner. I think that it is worth learning functional programming purely for the intellectual challenge.

Author:	Prabhakar Ragde [ Fri May 14, 2010 4:53 pm ]
Post subject:	Re: How is functional programming useful
bbi5291 @ Fri May 14, 2010 3:28 pm wrote: I found functional programming much more difficult to learn than imperative programming. For someone who knows neither, functional programming is easier to learn than imperative programming. For someone who knows imperative programming, functional programming will seem harder, because you have to stop thinking in a manner you've grown accustomed to. You are right that the intellectual challenge alone is worthwhile, but I also believe that the exposure makes you a better imperative programmer.

Author:	Tony [ Fri May 14, 2010 5:11 pm ]
Post subject:	Re: How is functional programming useful
Prabhakar Ragde @ Fri May 14, 2010 4:53 pm wrote: the exposure makes you a better imperative programmer. QFT. Especially with multi-paradigm languages (I'm thinking Ruby in specific, but Python also works for this) -- I employ OOP, imperative, and functional approaches to parts, as I see fit. While the same language could be used with just a single paradigm, the ability to use multiple ones is very powerful and gives you more options to solve problems.

Author:	Prabhakar Ragde [ Fri May 14, 2010 5:16 pm ]
Post subject:	Re: How is functional programming useful
Tony @ Fri May 14, 2010 5:11 pm wrote: While the same language could be used with just a single paradigm, the ability to use multiple ones is very powerful and gives you more options to solve problems. Your point is certainly valid, Tony, but I was saying something stronger. We wouldn't call C a multi-paradigm language. But I think that learning functional programming makes you a better C programmer.

Author:	DtY [ Fri May 14, 2010 7:09 pm ]
Post subject:	RE:How is functional programming useful
Functions can be passed and returned in functions in C, wouldn't that make it functional?

Author:	Prabhakar Ragde [ Fri May 14, 2010 8:29 pm ]
Post subject:	RE:How is functional programming useful
Only functions that exist at compile time. A functional language permits you to create functions at run time.

Author:	jcollins1991 [ Fri May 14, 2010 8:34 pm ]
Post subject:	Re: RE:How is functional programming useful
DtY @ Fri May 14, 2010 7:09 pm wrote: Functions can be passed and returned in functions in C, wouldn't that make it functional? Not sure if you're serious or not, so I'll answer anyways... Functional programming is more about treating functions more like mathematical functions, where for any given input to a function there's only one output... IMO the description in wikipedia is pretty good...

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy