Function arithmetic?

Over the summer I learned a bit of PHP and javascript, so I figured I would also get a head start on math for this year, which, for me, will be calculus. I was watching some videos and came across this:

http://www.youtube.com/watch?v=K6hxKU1kWUs&feature=mfu_in_order&list=UL

He says that (f+g)(x)=f(x)+g(x). I've never seen functions written like that, so I thought I would ask if this is implemented in programming languages too.

Assuming I have, in pse开发者_如何学编程udo-code:

function double(x){
return x*2;
}
function triple(x){
return x*3;
}

Is there any programming language that would allow something like:

(double + triple)(10)

...to equal 50?

Also, is there a place I can learn calculus from a source that isn't 10000 years old?

also, I'm aware that no programming language would work with this exact syntax, but I mean something similar...

---

How to do it

In Haskell, this is actually very easy:

Prelude Control.Monad> liftM2 (+) (* 2) (* 3) 10
50

Or, alternatively:

Prelude Control.Applicative> (+) <$> (* 2) <*> (* 3) $ 10
50

Or, more verbosely:

import Control.Monad

main :: IO ()
main = do let (+$)   = liftM2 (+) -- Define a new infix operator
          let double = (* 2)
          let triple = (* 3)
          print $ (double +$ triple) 10

What's happening here? Haskell's a very alien language if your experience lies in PHP and JavaScript, so I'll try to break it down. But just a heads up: the relevant functions here (liftM2 and <$>/<*>) are much more general than simply this usage, which can make understanding them difficult at first. The resulting power, however, is worth it.

---

High-level summary

Here's my attempt at a very high level summary: liftM2 takes a binary function op and produces a binary function which operates on "more complicated" values. If your "more complicated" values are one-argument functions f and g, there's only one good way to combine them and produce a new one-argument function: produce a function which passes its argument x to f and to g, and then computes f x `op` g x—it combines their results by using op. In JavaScript, this would be something like

function liftM2_functions(op) {
  return function (f,g) {
    return function (x) { op(f(x), g(x)) }
  }
}

Since liftM2 only works on binary functions, there's also liftM3 for ternary functions, and so on, but this is messy; thus, the <$> and <*> operators were introduced, such that liftMn f a1 a2 ... an is exactly equivalent to f a1 <*> a2 <*> ... <*> an.

---

Details

If you want a much more detailed answer, read on. I will warn you that I'm not sure how clear this is; it relies on some concepts which I have to semi-handwave, and I may not have done a good job. But if you're game, here we go.

First, let's just explain some Haskell syntax:

• (* 2) and (* 3) are short-hand ways of writing \x -> x*2 and \x -> x*3, which are just Haskell for the JavaScript function (x) { return x*2 } and function (x) { return x*3 }.
• (+) is just the function which performs addition; it's the prefix form of the infix operator +.
• f x is function application f(x); f x y is parsed as (f x) y, but can be considered two-argument function application f(x,y).
• The $ infix operator is also function application, but with lower precedence: ... $ x is parsed as (...) x.
• <$> and <*> are fancy infix operators.

Types

So! With that out of the way, let's consider the first snippet first. In liftM2 (+) (* 2) (* 3) 10, the "function addition function" you want is liftM2 (+); its two arguments are (* 2) and (* 3); and the argument to the result of that is 10. What's going on? In Haskell, the right way to think about this is in terms of types. Here are the relevant types—but be warned, you probably won't understand them immediately.

liftM2 :: Monad m => (a -> b -> r) -> m a -> m b -> m r
(+)    :: Num a => a -> a -> a
(* 2)  :: Num a => a -> a
(* 3)  :: Num a => a -> a
10     :: Num a => a

Here, f :: t means "f has the type t". These types are pretty abstract, so lets simplify some things. When you see Num a, it means "for some type a which is a number"; we can think about this as, for instance, Int or Double. So that gives us

(+)    :: Int -> Int -> Int
(* 2)  :: Int -> Int
(* 3)  :: Int -> Int
10     :: Int

Alright, 10 is an integer. And what about (* 2) and (* 3)? These are functions, denoted by the ->, which map an integer to an integer. You know that (+) is a binary function on integers, so you might think it would have the type (Int,Int) -> Int. However, in Haskell, the right way to think about this is as a function which takes an integer and returns another function; this is called currying. In JavaScript, this would be implemented as

function add(x) {
  return function (y) {
    return x + y
  }
}
// Usage: add(10)(11) = 21.

You might not understand why this is good, but it will become relevant in a bit.

Now, let's tackle liftM2 :: Monad m => (a -> b -> r) -> m a -> m b -> m r. What on earth is going on here? Ignoring the Monad m bit, this says that liftM2 takes a two-argument function, a "monadic a", and a "monadic b", and produces a "monadic r". However—thanks to currying—this is the same as saying that liftM2 takes a two-argument function and returns a two-argument function whose arguments and results are monadic: liftM2 :: Monad m => (a -> b -> r) -> (m a -> m b -> m r). So that's what's happening here: liftM2 (+) is a monadic version of addition.

Monads (don't panic!)

Now, I keep using the word monadic, and I haven't defined it. And I'm not going to! There are plenty of monad tutorials on the web, and some are even good; if you're curious, check out "You Could Have Invented Monads!". Here's all you need to understand for the moment: a monadic value is one which is "augmented" in some way, by having some extra structure around it. Since lists are a monad, [1,2,3] is a monadic int in the list monad; there, the structure is that it's an int which could be either one or two or three. We are concerned with the reader monad here: a monadic int in this case is just a function which takes some object of type a and returns an int. The idea is that it's an integer which can read and depend on some environment.

So, what we have here is exactly that. (* 2) is a function which takes and returns an integer. Specializing the type of liftM2 to use the reader monad, we end up with the following:

liftM2 :: (a -> b -> r) -> ((e -> a) -> (e -> b) -> (e -> r))

Now this is promising! The liftM2 function is taking a binary function, and producing a function which itself acts on functions. Applying it to (+) :: Int -> Int -> Int, we get

liftM2 (+) :: (e -> Int) -> (e -> Int) -> (e -> Int)

If you think about it, this is the type of addition of functions: liftM2 (+) takes two one-argument functions, and produces a new one-argument function, and it does so by adding their results.

Now, how is liftM2 implemented? Like so (a reformatted version of the real implementation):

liftM2 f m1 m2 = do x1 <- m1
                    x2 <- m2
                    return $ f x1 x2

What's going on here? This says "get a value of type a out of m1, get another out of m2, and combine those values with the given f". Inside our reader monad (single-argument functions), m1 :: e -> Int, and x1 <- m1 applies m1 to the "environment", which in our example is 10. So in our case, we have

do doubled <- (* 2)
   tripled <- (* 3)
   return $ doubled + tripled

This whole expression, of course, must depend on the mystery environment, since I've never mentioned it anywhere. So its type is Int -> Int: a function which takes an int, doubles and triples it, and ads the two together. Which is, of course, where we started.

Applicative functors (keep not panicking!)

What about <$> and <*>? I explained them at a very high level above, and I can tell you the basic idea: <$> is like a liftM1 function, and <*> applies "complicated" functions to "complicated" values. Their actual types are

(<$>) :: Functor f => (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

I'm not going to explain these in detail here, because I don't think I can do a very good job. In one sentence, an object in a functor is in some sense a plain value with extra complications, and <$> (also called fmap) leaves the complications alone and applies a function to the plain old value inside. And <*> is part of the extra structure which allows you to apply functions to multiple plain values inside multiple structures at once. But if you want more information, it's out there (although I don't know a good resource—people often recommend Learn You A Haskell, though).

---

Conclusion

By leveraging some powerful constructs (applicative functors and/or monads), we can get this notion of function addition basically for free, and lots more besides. (Function multiplication? liftM2 (*). Function-level if-then-else? liftM3 if' where if' c t f = if c then t else f. And so on.) And the great thing about Haskell is that these advanced features are baked in. Functors and monads are defined in the Prelude, the module which is implicitly included in every Haskell program (like Java's java.lang namespace); the Control.Monad module (which defines liftM2) and the Control.Applicative module (which defines applicative functors, <$>, and <*>) are part of the standard library¹. Haskell's higher-order and statically-typed nature allows it to leverage these concepts; doing this in PHP or Java would be basically impossible, and while JavaScript could express some of the concepts, the fact that it's dynamically typed means that the implementation would have to look very different. Other languages such as Scala can and do leverage these concepts as well, although Scala's the only one I can think of off the top of my head (and they are provided in Scalaz, not the standard library). The take-home message is that having access to these high-powered abstractions allows you to write simpler code, and less of it, to do the less-abstract things—such as function addition—that you want to do.

---

1: To be fair, Control.Applicative is not in the Haskell 2010 standard. However, it is included by default with GHC, by far the most used Haskell compiler (it's the de-facto standard), as well as Hugs (a Haskell interpreter which had significant usage but has been losing ground to GHC), and as far as I can tell, JHC and YHC (two other compilers) as well. And there's nothing stopping an unrelated Haskell compiler from building Control.Applicative, as the code is completely conformant to Haskell 2010.

---

Most languages let you do this one way or another...

function add(a, b) {
    return function(x) {
        return a(x) + b(x);
    };
}

add(double, triple)(10);  // Gives 50

---

You could do that easily in Scala:

abstract class F { f =>
  def apply(x: Double): Double
  def +(g: F) = { new F { def apply(x: Double) = f(x) + g(x) } }
}
object F {
  implicit def funcToF(f: Double => Double) = new F { def apply(x: Double) = f(x) }
}

import F.funcToF

val f = (x: Double) => 2*x
val g = (x: Double) => 3*x

val h = f + g
println(f(1))        // 2
println(g(1))        // 3
println(h(1))        // 5
println((f + g)(1))  // 5

You can try it online at http://www.simplyscala.com

---

@Antal has posted an excellent answer to your question. I will post the Scala version of his applicative solution (using the fantastic Scalaz library):

scala> import scalaz._
import scalaz._

scala> import Scalaz._
import Scalaz._

scala> val double = (x: Int) => 2 * x
double: (Int) => Int = <function1>

scala> val triple = (x: Int) => 3 * x
triple: (Int) => Int = <function1>

scala> val h = (double |@| triple) { _ + _ }
h: (Int) => Int = <function1>

scala> h(10)
res13: Int = 50