functional-programming - Do pure functions have only one possible implementation?

Question

In the image below there is a quick explanation, why pure functions appear to have only one possible implementation.
I don't really get the idea because (++) : ('a -> 'b) -> ('a -> 'b) -> 'a -> 'b for example can clearly be implemented by let (++) (f: ('a -> 'b)) (g: ('a -> 'b)) x = f x or
let (++) (f: ('a -> 'b)) (g: ('a -> 'b)) x = g x
Is that image just wrong or do I miss something here?

标签： functional-programmingocaml

Answer 1

You are right. The attached image is incorrect even without type annotations.

At first, it's important to consider what kind of "equality" on implementations is assumed here. Let's consider the following examples.

1. Is (@@) equal to (@@+)?

   let ( @@ ) f x = f x
   let ( @@+ ) f x =
     let _ = 42 in
     f x
   

2. Is (|>) equal to (|>+)?

   let ( |> ) x f = f x
   let ( |>+ ) x f = f @@ x
   

3. Is (%) equal to (%+)?

   let ( % ) f g x = f (g x)
   let ( %+ ) p q r = p (q r)
   

If (@@) is not equal to (@@+), then we can construct the 5th implementation of a function bool -> bool, such as (fun x -> let _ = 42 in true).

Therefore, the author of the image would have wanted to distinguish functions not by its implementation (or codes), but by some other element such as its behavior (like duck test or the equality on mathematical functions).

Still, the image is incorrect. The image claims "for pure functions that don't have any concrete type in the signature, there is only one possible implementation", but no. For example, there is no pure function 'a -> 'b. This can be shown through the Curry–Howard correspondence.