overview, but very over in functional programming

What does a very general function look like in functional programming?

Somebody said "we don't have objects, but we have higher order functions". Do higher order functions replace objects?

While programming object-oriented apps, I try to go from a more general to a more detailed idea, lots of times. If I try to do that in functional progr开发者_C百科amming, am I going to need lots of higher order functions?

This answer is oriented towards Haskell rather than Lisp because although lisp has higher order functions, idiomatic lisp can be and is often very object-oriented.

We'll also ignore inheritance (and ad-hoc polymorphism) which is commonly associated with object oriented programming, but is somewhat orthogonal.

In general, abstract data types "replace" objects, in the sense that generally you use an object to bundle together a bunch of related data in e.g. Java or Python, and you declare a data type to do such a thing in Haskell or ML.

However objects also bundle behavior with the data. So an object of a class has data, but also functions which can access and mutate that data. In a functional style, you'd simply declare the functions on your data type outside of that data type. Then encapsulation is provided by either modules or use of closures.

On the latter point -- closures and objects are duals, although it is not necessarily idiomatic to express them as such. There's some very old-school discussion of this at the portland patterns wiki: http://c2.com/cgi/wiki?ClosuresAndObjectsAreEquivalent.

Oh, and an example from oleg: http://okmij.org/ftp/Scheme/oop-in-fp.txt.

Ignoring typeclasses (which are essential to idiomatic Haskell), and focusing just on core functional programming, here's a sketch of a different approach to something that would be done with inheritance in an OO language. Function foo uses some object that implements interface A and some object that implements interface B to produce some Double. With higher order functions, you'd perhaps have a type signature of fooGen :: (a -> Double -> Double) -> (b -> String -> Double) -> a -> b -> Double.

That signature says that fooGen takes a function from some a and a Double to another Double, and a function of some b and a String to a Double, and then it takes an a and a b, and finally it returns a Double.

So now you can pass in the "interface" separately from the concrete values through partial application, by declaring, e.g., fooSpecialized = fooGen funcOnA funcOnB.

With typeclasses, you can abstract away the concrete passing in of the "interface implementation" (or, in more proper language, dictionary), and declare foo :: HasSomeFunc a, HasSomeOtherFunc b => a -> b -> Double. You can think of the stuff on the left hand side of the => as declaring, loosely, the interfaces that your concrete a and b types are required to implement.

This is all a handwavy and partial answer of course to an exceedingly general question.

Answers first

Somebody said "we don't have objects, but we have higher order functions". Do higher order functions replace objects?

If you mean can higher order functions contain some hidden state, then yes. Functions defined inside of the other functions can capture some information from their scope, and, if returned to the outer world, will preserve this information. This is what closures are about.

If you mean can higher order functions contain mutable state, then no. In pure functional programming they are not stateful. They produce the same results on the same inputs. If you want to simulate how something changes, you do not overwrite a variable, but you define how to calculate its new value from the old one.

Of course, there are shortcuts, and even functional languages allow for writing in imperative style.

If I try to do that in functional programming, am I going to need lots of higher order functions?

You are going to use them a lot. Probably not even thinking that your functions are higher-order. And probably, enjoying them a lot. You'll just pass functions as values to other functions.

For example, map is a HOF. Its first argument is another function. What you would think of in an imperative language as a loop "for every element in a collection: apply some function, save the result", in the functional language will be "map a function over a collection and get a new collection of results". Folds are another example of HOFs. So most of the loops from an imperative language can be translated to the calls of a higher order functions in a functional language. This is to make clear how often you are likely to use them.

overview, but very over in functional programming

This is a good place to start: Functional Programming.

An example of encapsulating "state":

f = let x = 3
    in  let withX y = x + y
        in  withX

Now f is the same as withX, which is a function that "remembers", that x = 3. When we use f, we need to supply only one argument, y, and it will sum it with the "remembered" value of x (3).

This should print 3 and then [4, 5, 6]:

main = do
  print $ f 0
  print $ map f [1..3]

We do not pass 3 as an argument to f, it "remembers" 3 from the closure above, and we can pass f itself as a parameter to map, which is a HOF in this case.

So functions can encapsulate state.

An example of "changing" a variable

As I said above, in functional programming, the state is not mutable. So if you want to, say, apply operation f to the value, save the result, and then apply operation g, in functional language you would express it with an intermediate variable, which contains the result of applying f, and then apply g to it to calculate the new value. Please note that you are not "overwriting" the original value x0:

applyTwo first second x0 =
  let x1 = first x0
  in  second x1

But in fact it is possible to write it shorter, because it is just a simple composition of functions:

applyTwo' f g = g . f

Or you can generalize this approach, and write a function, which will apply any number of functions:

applyAll []          = id       -- don't do anything if there are no functions to apply
applyAll (f:otherFs) = applyAll otherFs . f

Please note, that applyTwo and applyAll are now a higher order functions. Of course, they do not replace objects, but allow to avoid the mutable state.

This how they are used:

ghci> applyTwo (+1) (*10) 2
30
ghci> applyAll [(+1), (*10)] 2
30

It's all programming; the same patterns show up again and again. You might write something like this in your favorite OO language:

role Person {
   has 'firstname' => ( isa => 'Str' );
   has 'lastname'  => ( isa => 'Str' );
}

class Employee does Person {
   has 'manager' => ( isa => 'Employee'   );
   has 'reports' => ( isa => '[Employee]' );
}

Whereas in Haskell, you'd write:

class Person a where
    firstname :: a -> String
    lastname  :: a -> String

data Employee = Employee { firstName :: String
                         , lastName  :: String
                         , manager   :: Employee
                         , reports   :: [Employee]
                         }

instance Person Employee where
    firstname = firstName
    lastname  = lastName

People worry too much about what's different rather than realizing that most things are the same.