How do free point functions actually "function"?

Question

Conal argues here that types with zero construction are not functions. However, dotless functions are described as such, for example, on Wikipedia , when they do not take explicit arguments in their definitions, and it seems to be more of a currying property, How exactly do they function?

In particular: how f = map and f = id . map differ f = id . map f = id . map in this context? Like in, f = map is simply a binding to a value, which turns out to be a function, where f simply "returns" map (just like f = 2 "returns" 2 ), which then takes arguments, But f = id . map f = id . map is called a function because it has no points.

Answer 1

A Conal blog post boils down to “non-functions not functions”, for example. False not a function. This is pretty obvious; if you take into account all possible values ​​and delete those that have the type of function, then those that remain are ... not functions.

This has absolutely nothing to do with the concept of point 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) = fx : map4 f xs 

These are all definitions of the same function (and there are many more ways to define something equivalent to the map function). map1 is obviously a point definition; map4 is obviously not. They also both obviously have the type of function (the same one!), So how can we say that point definitions are not functions? Only if we change our definition of "function" to something other than what is usually implied by Haskell programmers (that the function is something like 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" (with decreasing point?); the definition calls its first argument f , but does not mention the second argument.

The point in all of this is that point-free-ness is the quality of definitions , and being a function is a property of values . The concept of a point function does not really make sense, since this function can be defined in many ways (some of them have no points, while others do not). Whenever you see someone talking about a trouble-free function, it means a trouble-free definition.

You seem to be worried that map1 = map not a function, because it is just a binding to the existing map value, like x = 2 . You are mixing concepts here. Remember that features are second to none in Haskell; “things that are functions” is a subset of “things that are values” and not for another class! Therefore, when map is an existing value, which is a function, then yes map1 = map simply binds the new name to the existing value. It is also defining the function map1 ; these two are not mutually exclusive.

You answer the question “is it useless” by looking at the code; function definition. You answer the question “is this a function” by looking at types.

Answer 2

Contrary to what some people may think, everything in Haskell is not a function. Jokes aside. Numbers, strings, booleans, etc. They are not functions. Even null functions.

Nukal functions

A null function is a function that takes no arguments and performs some “side effects”. For example, consider this null JavaScript function:

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

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

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

Unary functions

In contrast, functions in Haskell can never be null. In fact, functions in Haskell are always unary. Functions in Haskell always take one and only one argument. Haskell multiparameter functions can be modeled either using currying or using multiple-field data structures.

 add' :: Int -> Int -> Int -- an example of using currying add' xy = 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 is a data type, like any other data type that you can define in Haskell. However, functions are special because they are contravariant in the type of the argument and covariant in the return type .

When you define a new type of algebraic data, all the fields of its type constructors are covariant (i.e., a data source) instead of contravariant (i.e., a data stream). A covariant field creates 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 fields field1 , field2 and field3 are covariant. They create data like 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 ab = Function { domain :: a -- the argument type , codomain :: b -- the return type } 

Of course, a function is not really defined as follows, but suppose it is. The function has two fields domain and codomain . When we create a value of type Function , we do not know either of these two fields.

• We do not know the value of domain , because it is contravariant. Therefore, it must be provided by the user.
• We do not know the meaning of codomain because, although it is covariant, it may depend on domain , and we do not know the value of domain .

For example, \x -> x + x is a function where the domain value is x and the codomain value is x + x . Here, domain is contravariant (i.e., a data stream), since the data enters the function through domain . Similarly, codomain is covariant (i.e., a data source), since data is derived from a function through codomain .

The fields of algebraic data structures in Haskell (for example, Foo , which we defined earlier) are all covariant, since the data from these data structures is through its fields. Data never falls into these structures, as is done for the domain function field. Therefore, they are never contravariant.

Multiparameter Functions

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

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

 [-] -> [+] 

Now the domain and coded functions can be individually replaced with other types. For example, in currying, a coded function is another function:

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

Note that when a covariant type is replaced by another type, the variance of the new type is preserved. This makes sense because it is equivalent to a function with two arguments and one return type.

On the other hand, if we replaced the domain with another function:

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

Note that when we replace a contravariant type with another type, the variance of the new type is inverted. This makes sense, because although ([+] -> [-]) is generally contravariant, its input type becomes the output of the entire function, and its output type becomes the input of the entire function. For instance:

 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 multi-parameter functions, because when one function returns another function, we get several inputs and one output, because for the returned type, saving is saved:

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

A data structure with multiple fields as a function domain also emulates multi-parameter functions, because the variance is inverted for the type of the function argument:

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

Not function

Now, if you look at values ​​such as numbers, strings, and booleans, these values ​​are not functions. However, they are still covariant.

For example, 5 displays the value 5 . Similarly, Just 5 creates a value of Just 5 and fromJust (Just 5) produces a value of 5 . None of these expressions consume meaning, and, therefore, none of them is contravariant. However, in Just 5 , the Just function consumes a value of 5 , and in fromJust (Just 5) , the fromJust function consumes a value of Just 5 .

So, everything in Haskell is covariant, with the exception of function arguments (which are contravariant). This is important because each expression in Haskell must evaluate the value (i.e., produce the value, not consume the value). At the same time, we want functions to consume a value and produce a new value (hence, facilitate data conversion, beta reduction ).

The final effect is that we can never have a contravariant expression. For example, the expression Just is covariant, and the expression Just 5 also covariant. However, in the Just 5 expression, the Just 5 function consumes the value 5 . Therefore, contravariance is limited by functional arguments and limited by the scope of the function.

Since every expression in Haskell is covariant, people often think of non-functional values, such as 5 as "null functions". Although this intuition is insightful, but it is wrong. The value 5 not a null function. This is an expression that cannot be shortened by beta. Similarly, the value fromJust (Just 5) not a null function. This is an expression that can be shortened to 5 , which is not a function.

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

Precise and Accurate Functions

Now consider the function \x -> x + x . This is a point function, because we explicitly declare the argument of the function, giving it the name x .

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

Note that join (+) is a function because beta comes down to the function \x -> x + x . This is not like a function because it has no points (i.e., explicitly declared arguments). However, this is still a feature.

Pointfree functions have nothing to do with currying. Pointfree functions are dot-free write functions (for example, join (+) instead of \x -> x + x ). Currying is when one function returns another function, thereby allowing a partial application (for example, \x -> \y -> x + y , which can be written in style without restrictions as (+) ).

Name binding

In the f = map binding, we simply specify map alternative name f . Note that f does not return map . This is just an alternate name for map . For example, in the x = 5 binding, we are not saying that x returns 5 because it is not. The name x not a function or value. It is simply a name that identifies the value 5 . Similarly, in f = map name f simply identifies the value of map . The name f is called the designation of the function, because map means the function.

Linking f = map does not make sense because we have not explicitly declared any arguments to f . If we wanted, then we could write fg xs = map g xs . That would be an accurate definition, but due to eta conversion we can write it more briefly in non-contact form as f = map . The concept of an eta transformation is that \x -> fx equivalent to f itself and that the point \x -> fx can be converted to pointfree f and vice versa. Note that fg xs = map g xs is just syntactic sugar for f = \g xs -> map g xs .

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

Just remember that f not a function that "returns" id . map id . map . This is just the name specified for the id . map expression id . map id . map for convenience.

PS To enter zero functions for free:

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