Do you need a functional programming language to program functionally?

tinyTux · 04-13-2011, 04:12 PM

Be patient with me, here, but I was getting started on learning Haskell through the intro guide at http://www.haskell.org/haskellwiki/Introduction. It has the big section about how two lines of functional code in Haskell equals two dozen lines of imperative code in C. The Haskell code was:

Code:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

And the C code was:

Code:

// To sort array a[] of size n: qsort(a,0,n-1)

void qsort(int a[], int lo, int hi) 
{
  int h, l, p, t;

  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];

    do {
      while ((l < h) && (a[l] <= p)) 
          l = l+1;
      while ((h > l) && (a[h] >= p))
          h = h-1;
      if (l < h) {
          t = a[l];
          a[l] = a[h];
          a[h] = t;
      }
    } while (l < h);

    a[hi] = a[l];
    a[l] = p;

    qsort( a, lo, l-1 );
    qsort( a, l+1, hi );
  }
}

And that makes sense, of course, if you program it in C in an imperative manner. But couldn't you just program it in a functional manner, and create basically the equivalent code? I didn't want to do that in C, 'cause I didn't want to mess around with the issue of array sizes. But in Ruby, this works fine: (usage code included)

Code:

def qsort(arr)
  if arr.length == 0
    return []
  else
    return [qsort([ arr.reject {|x| x >= arr[0]} ].flatten), arr[0], qsort([ arr.reject {|x| x <= arr[0]} ].flatten)].flatten
  end
end

arr = [5, 2, 8, 3]
new_arr = qsort(arr)
puts new_arr

I sure there are other reasons to use Haskell, of course, I'm just asking: If you use an "imperative" language to program "functionally" what's the big difference?

paulsm4 · 04-14-2011, 01:21 AM

I suppose similar arguments were made about whether you could do "object oriented" programming in procedural languages like FORTRAN or Pascal.

Clearly, functional programming is easier in languages that specifically support it, like Erlang or Haskell.

Interestingly, Javascript (arguably the most-used language on the planet!) supports functional programming extremely well. So well, in fact, lots of "functional code" is probably out there without the developer even realizing he/she was DOING "functional programming!

So I guess my reply to your question is: "Whatever works

!"

'Hope that answers your question ... at least partially.

Ramurd · 04-14-2011, 01:31 AM

Quote:

I suppose similar arguments were made about whether you could do "object oriented" programming in procedural languages like FORTRAN or Pascal.

reminds me of that guy that could do object-oriented programming in assembly.

Reasons for learning a language or not is affinity of other developers with the language, learning curve and apart from that: most languages are good/best practice for a specific type of task. Some languages are extremely well in data-organization, whereas others are best for low-level system resources, others have a tendency to be good for general-purpose; and so every language has strengths and weaknesses.

As for this line of code:

Code:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

It's an instant "no" for me; this is so unreadable; nice that you saved a few keystrokes, but how do you go about debugging them?

JohnGraham · 04-14-2011, 03:42 AM

Quote:

Originally Posted by tinyTux

I sure there are other reasons to use Haskell, of course, I'm just asking: If you use an "imperative" language to program "functionally" what's the big difference?

Not a lot - although there might be some pitfalls, especially with C. For example, one defining characteristic of programs written in a functional style is that their functions return new objects without changing the old ones. For example, in the following LISP code:

Code:

(reverse (mapcar #'double x))

The mapcar function takes a function (#'double) and a list (x) and returns a brand-new list (let's call it 'y'), and then the reverse function takes that list and returns another brand-new list (let's call it 'z'). Well, in a language where you want to do that, you need to have garbage collection - in C, the list 'y' would have been allocated on the heap, but we've lost all references to it, and so have a memory leak.

Off the top of my head, garbage collection is probably the most important thing to have in order to program in a functional style - so long as you have that, go for it.

(Edit: Other things that will help a lot are having functions as first-class objects and lexical closures, but they're not essential.)

Sergei Steshenko · 04-14-2011, 07:26 AM

In this context functional languages discipline your mind - they teach you to formulate problems and their solutions concisely, with strict mathematical flavor, omitting (when|where)ever possible implementation details, like, for example, traditional loops.

MTK358 · 04-14-2011, 07:49 AM

Quote:

Originally Posted by Ramurd

As for this line of code:

Code:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

It's an instant "no" for me; this is so unreadable; nice that you saved a few keystrokes, but how do you go about debugging them?

I agree.

I tried to start learning Haskell at least 2 or 3 times, but gave up becasue even the basic, beginner tutorials had such unreadable gibberish for code that I just couldn't figure it out.

Sergei Steshenko · 04-14-2011, 09:35 AM

Quote:

Originally Posted by MTK358

I agree.

I tried to start learning Haskell at least 2 or 3 times, but gave up becasue even the basic, beginner tutorials had such unreadable gibberish for code that I just couldn't figure it out.

Have you tried to learn a foreign language without first learning the alphabet (if it's an alphabetic language) ?

tinyTux · 04-15-2011, 12:49 PM

I need to study into this more. Upon further reflection, I discovered there are some other issues here I don't understand well enough yet, such as dealing with state in a functional program (i.e., monads), as well as if and how the object-oriented paradigm can integrate with the functional one. These questions seem to be the most significant of any, and yet are the most puzzling.

Sergei Steshenko · 04-15-2011, 01:12 PM

Quote:

Originally Posted by tinyTux

I need to study into this more. Upon further reflection, I discovered there are some other issues here I don't understand well enough yet, such as dealing with state in a functional program (i.e., monads), as well as if and how the object-oriented paradigm can integrate with the functional one. These questions seem to be the most significant of any, and yet are the most puzzling.

OO is a formal consequence of functional. State in OO is well reflected by closures in functional. Virtual methods are essentially arguments which are functions.

Monads:

http://en.wikipedia.org/wiki/Monad_%...programming%29
http://stackoverflow.com/questions/3...gramming-terms
.

And the biggest question is: why one needs OO in the first place ?

MTK358 · 04-15-2011, 01:16 PM

Quote:

Originally Posted by Sergei Steshenko

And the biggest question is: why one needs OO in the first place ?

Do you mean real OO languages, or OO itself, even faked with functional techniques?

Sergei Steshenko · 04-15-2011, 02:45 PM

Quote:

Originally Posted by MTK358

Do you mean real OO languages, or OO itself, even faked with functional techniques?

I mean OO paradigm.

MTK358 · 04-15-2011, 02:53 PM

Quote:

Originally Posted by Sergei Steshenko

I mean OO paradigm.

Still, by "paradigm" do you mean OO built into a language or use of OO-like techniques?

Sergei Steshenko · 04-15-2011, 03:10 PM

Quote:

Originally Posted by MTK358

Still, by "paradigm" do you mean OO built into a language or use of OO-like techniques?

By paradigm I mean paradigm.

tinyTux · 04-19-2011, 11:53 AM

I hate to eat my own hat, so to speak, but I spent some more time learning Haskell, as well as trying to apply functional programming principles in other languages, namely, Ruby and C++.

Starting off, C++ was very difficult for two reasons primarily: 1) No automatic memory management, and 2) one cannot return lists or arrays (only pointers to them). So you have a lot of mess to deal with deciding when to malloc and free stuff, which gets quite complicated in recursive functions. These two worked together to make creating pure and recursive functions quite impractical. Not to say one couldn't figure out workarounds, but it showed me that C++ was poorly fit for true functional programming.

Ruby is much better, but the wrenching difficulty is that Ruby does not support tail call optimization, meaning that you can't create tail-recursive functions without dealing with monster-like stack growth. Especially a problem if you want to create infinitely recursive functions to replace main loops and other such "imperative" constructs. Ruby 1.9 does have tail call optimization capability, but it is not enabled by default (because it would interfere with the compiled-in stack-trace functionality) and the capability is not actually guaranteed by the specification, but it is actually up to the implementation whether or not to include it.

Working with Haskell some more, it seems to me like Haskell provides a lot of unique language constucts that are better suited to the general functional paradigm; that is, wrapping programming into mathematical-like formulas, rather than simply listing sequences of commands. Programming in Haskell can actually be rather fun if you adopt the right mindset for it.