How are point-free functions actually "functions"?

Question

Conal here argues that nullary-constructed types are not functions. However, point-free functions are described as such for example on Wikipedia, when they take no explicit arguments in their definitions, and it seemingly is rather a property of currying. How exactly are they functions?

Specifically: how are f = map and f = id . map different in this context? As in, f = map is simply just a binding to a value that happens to be a function where f simply "returns" map (similar to how f = 2 "returns" 2) which then takes the arguments. But f = id . map is referred to as a function because it's point-free.

Answer 1

Conal's blog post boils down to saying "non-functions are not functions", e.g. False is not a function. This is pretty obvious; if you consider all possible values and remove the ones which have a function type, then those that remain are... not functions.

That has absolutely nothing to do with the notion of point-free definitions.

Consider the following function definitions:

map1, map2, map3, map4 :: (a -> b) -> [a] -> [b]

map1 = map

map2 = id . map

map3 f = map f

map4 _ [] = []
map4 f (x:xs) = f x : map4 f xs

These are all definitions of the same function (and there are infinitely many more ways to define something equivalent to the map function). map1 is obviously a point-free definition; map4 is obviously not. They also both obviously have a function type (the same one!), so how can we say that point-free definitions are not functions? Only if we change our definition of "function" to something else than what is usually meant by Haskell programmers (which is that a function is something of type x -> y, for some x and y; in this case we're using a -> b as x and [a] -> [b] for y).

And the definition of map3 is "partially point-free" (point-reduced?); the definition names its first argument f, but doesn't mention the second argument.

The point in all this is that "point-free-ness" is a quality of definitions, while "being a function" is a property of values. The notion of point-free function doesn't actually make sense, since a given function can be defined many ways (some of them point-free, others not). Whenever you see someone talking about a point-free function, they mean a point-free definition.

You seem to be concerned that map1 = map isn't a function because it's just a binding to the existing value map, just like x = 2. You're confusing notions here. Remember that functions are first-class in Haskell; "things that are functions" is a subset of "things that are values", not a different class of thing! So when map is an existing value which is a function, then yes map1 = map is just binding a new name to an existing value. It's also defining the function map1; the two are not mutually exclusive.

You answer the question "is this point-free" by looking at code; the definition of a function. You answer the question "is this a function" by looking at types.

Answer 2

Contrary to what some people might believe everything in Haskell is not a function. Seriously. Numbers, strings, booleans, etc. are not functions. Not even nullary functions.

Nullary Functions

A nullary function is a function which takes no arguments and performs some “side-effectful” computation. For example, consider this nullary JavaScript function:

main();

function main() {
    alert("Hello World!");
    alert("My name is Aadit M Shah.");
}

Functions that take no arguments can only return different results if the are side-effectful. Thus, they are similar to IO actions in Haskell which take no arguments and perform some side-effectful computations:

main = do
    putStrLn "Hello World!"
    putStrLn "My name is Aadit M Shah."

Unary Functions

In contrast, functions in Haskell can never be nullary. In fact, functions in Haskell are always unary. Functions in Haskell always take one and only one argument. Multiparameter functions in Haskell can be simulated either using currying or using data structures with multiple fields.

add' :: Int -> Int -> Int -- an example of using currying
add'   x  y  = x + y

add'' :: (Int, Int) -> Int -- an example of using multi-field data structures
add'' (x, y) = x + y

Covariance and Contravariance

Functions in Haskell are a data type, just like any other data type you may define in Haskell. However, functions are special because they are contravariant in the argument type and covariant in the return type.

When you define a new algebraic data type, all the fields of its type constructors are covariant (i.e. a source of data) instead of contravariant (i.e. a sink of data). A covariant field produces data while a contravariant field consumes data.

For example, suppose I create a new data type:

data Foo = Bar { field1 :: Char, field2 :: Int }
         | Baz { field3 :: Bool }

Here the fields field1, field2 and field3 are covariant. They produce data of the type Char, Int and Bool respectively. Consider:

let x = Baz True -- I create a new value of type Foo
in  field3 x     -- I can access the value of field3 because it is covariant

Now, consider the definition of a function:

data Function a b = Function { domain   :: a -- the argument type
                             , codomain :: b -- the return   type
                             }

Ofcourse, a function is not actually defined as follows but let's assume that it is. A function has two fields domain and codomain. When we create a value of the type Function we don't know either of these two fields.

1. We don't know the value of domain because it is contravariant. Hence, it needs to be provided by the user.
2. We don't know the value of codomain because although it is covariant yet it might depend on the domain and we don't know the value of the domain.

For example, \x -> x + x is a function where the value of the domain is x and the value of the codomain is x + x. Here the domain is contravariant (i.e. a sink of data) because data goes into the function via the domain. Similarly, the codomain is covariant (i.e. a source of data) because data comes out of the function via the codomain.

The fields of algebraic data structures in Haskell (like the Foo we defined earlier) are all covariant because data comes out of those data structures via their fields. Data never goes into these structures like the way it does for the domain field of functions. Hence, they are never contravariant.

Multiparameter Functions

As I explained before, although all functions in Haskell are unary yet we can emulate multiparameter functions either using currying or fields with multiple data structures.

To understand this, I'll use a new notation. The minus sign ([-]) represents a contravariant type. The plus sign ([+]) represents a covariant type. Hence, a function from one type to another is denoted as:

[-] -> [+]

Now, the domain and the codomain of the function could each be individually replaced with other types. For example in currying, the codomain of the function is another function:

[-] -> ([-] -> [+]) -- an example of currying

Notice that when a covariant type is replaced with another type then the variance of the new type is preserved. This makes sense because this is equivalent to a function with two arguments and one return type.

On the other hand if we were to replace the domain with another function:

([+] -> [-]) -> [+]

Notice that when we replace a contravariant type with another type then the variance of the new type is flipped. This makes sense because although ([+] -> [-]) as a whole is contravariant yet its input type becomes the output of the whole function and its output type becomes the input of the whole function. For example:

function f(g) {       // g is contravariant for f (an input value for f)
    return g(x) + 10; // x is covariant for f (an output value for f)
                      // x is contravariant for g (an input value for g)
                      // g(x) is contravariant for f (an input value for f)
                      // g(x) is covariant for g (an output value for g)
                      // g(x) + 10 is covariant for f (an output value for f)
}

Currying emulates multiparameter functions because when one function returns another function we get multiple inputs and one output because variance is preserved for the return type:

[-] -> [-] -> [+]        -- a binary function
[-] -> [-] -> [-] -> [+] -- a ternary function

A data structure with multiple fields as the domain of a function also emulates multiparameter functions because variance is flipped for the argument type of a function:

([+], [+])        -- the fields of a tuple are covariant
([-], [-]) -> [+] -- a binary function, variance is flipped for arguments

Non Functions

Now, if you take a look at values like numbers, strings and booleans, these values are not functions. However, they are still covariant.

For example, 5 produces a value of 5 itself. Similarly, Just 5 produces a value of Just 5 and fromJust (Just 5) produces a value of 5. None of these expressions consume a value and hence none of them are contravariant. However, in Just 5 the function Just consumes the value 5 and in fromJust (Just 5) the function fromJust consumes the value Just 5.

So everything in Haskell is covariant except for the arguments of functions (which are contravariant). This is important because every expression in Haskell must evaluate to a value (i.e. produce a value, not consume a value). At the same time we want functions to consume a value and produce a new value (hence facilitating transformation of data, beta reduction).

The end effect is that we can never have a contravariant expression. For example, the expression Just is covariant and the expression Just 5 is also covariant. However, in the expression Just 5 the function Just consumes the value 5. Hence, contravariance is restricted to function arguments and bounded by the scope of the function.

Because every expression in Haskell is covariant people often think of non-functional values like 5 as “nullary functions”. Although this intuition is insightful yet it is wrong. The value 5 is not a nullary function. It is an expression which is cannot be beta reduced. Similarly, the value fromJust (Just 5) is not a nullary function. It is an expression which can be beta reduced to 5, which is not a function.

However, the expression fromJust (Just (\x -> x + x)) is a function because it can be beta reduced to \x -> x + x which is a function.

Pointful and Pointfree Functions

Now, consider the function \x -> x + x. This is a pointful function because we are explicitly declaring the argument of the function by giving it the name x.

Every function can also be written in pointfree style (i.e. without explicitly declaring the argument of the function). For example, the function \x -> x + x can be written in pointfree style as join (+) as described in the following answer.

Note that join (+) is a function because it beta reduces to the function \x -> x + x. It doesn't look like a function because it has no points (i.e. explicitly declared arguments). However, it is still a function.

Pointfree functions have nothing to do with currying. Pointfree functions are about writing functions without points (e.g. join (+) instead of \x -> x + x). Currying is when one function returns another function, thereby allowing partial application (e.g. \x -> \y -> x + y which can be written in pointfree style as (+)).

Name Binding

In the binding f = map we are just giving map the alternative name f. Note that f does not “return” map. It is just an alternative name for map. For example, in the binding x = 5 we don't say that x returns 5 because it doesn't. The name x is not a function nor a value. It's just a name which identifies the value of 5. Similarly, in f = map the name f just identifies the value of map. The name f is said to denote a function because map denotes a function.

The binding f = map is pointfree because we haven't explicitly declared any arguments of f. If we wanted to then we could have written f g xs = map g xs. This would be a pointful definition but because of eta conversion we can write it more succinctly in pointfree form as f = map. The concept of eta conversion is that \x -> f x is equivalent to f itself and that the pointful \x -> f x can be converted into the pointfree f and vice versa. Note that f g xs = map g xs is just syntactic sugar for f = \g xs -> map g xs.

On the other hand f = id . map is a function not because it is pointfree but because id . map beta reduces to the function \x -> id (map x). BTW, any function composed with id is equivalent to itself (i.e. id . f = f . id = f). Hence, id . map is equivalent to map itself. There's no difference between f = map and f = id . map.

Just remember that f is not a function that “returns” id . map. It is just a name given to the expression id . map for convenience.

P.S. For an intro to pointfree functions read:

What does (f .) . g mean in Haskell?