Partial functions and total functions | Hacker News Reader

Partial functions and total functions

johndcook.com

62 pointstacon20 comments

It kind of depends on the formalism. In one setting you imagine a universe of things U and a function f maps its domain D < U to its range R < U. In other words, D and R are derived properties of the function, f.

On the other hand, you might define a function as a triple (D, R, f) which lets us discuss, and then immediately outlaw, the idea of a value x in D such that f(x) is not-defined.

The most flexible approach is, as stated, to define relations as subsets of DxR first and then take functions to be a specialized subset of relations. Then we have exact ideas for what happens when a function fails to map the entire (explicitly stated) domain and can talk about other cool concepts like restrictions.

What means D < U in your notation? It's like, D is a subset of U?

Anyway the problem with trying to make a function total by fiat like with the definition (D, R, f) is that for some functions (even computable functions), its domain may be an uncomputable set.

That's because if we could decide if a given x in f(x) makes f return something or not, if f represents the output of a Turing machine we could use that to solve the halting problem.

So while in principle every function is total in some domain D (precisely the domain which it is defined to return some value), sometimes we can't talk very usefully about this domain. In this case, we choose to treat f as a partial function and talk about a larger set of values D' f receive as input (and might or might not return anything), for which D is a subset.

Some properties might not be literally undecidable but we may not know how to solve them yet. For example, the function collatz : Nat -> () [0] that receives a natural number and either return nothing if its collatz sequence[1] eventually reaches 1, or else run forever. What's the domain of this function? (you can switch this for any actually undecidable problem for extra hardness)

Unfortunately the linked article doesn't talk about this particular motivation for defining partial functions in computer science, and instead cites sqrt as an example, even though it has a perfectly computable domain. The domain of sqrt is just the non-negative reals; which we could give a more precise type to sqrt in if we have means to define the type of non-negative numbers (maybe using the smart constructors[2] technique, available in any programming language that lets you to define records/structs), which may or may not be ergonomic. We don't need dependent types for that, but they could be a tool to make this stuff ergonomic and actually check this at compile time (first class support for refinement types would also help).

[0] something like this

    fn collatz(n: natural) {
        while (n != 1) {
            if n % 2 == 0 {
                n <- n / 2;
            }
            else {
                n <- 3*n + 1;
            }
        }
    }

[1] https://en.wikipedia.org/wiki/Collatz_conjecture

[2] https://markkarpov.com/post/smart-constructors-that-cannot-f...

> On the other hand, you might define a function as a triple (D, R, f)

That's also the approach in Functional Analysis. Depending on how you choose D and R, some fundamental properties of the function change, e.g. bijectivity. Therefore specifying the sets is strictly speaking not optional.

The proper function definition in the other formalism would be rather:

f: D -> R: ...

Real-world implementations of mathematics always have limitations and the question is when to model them mathematically. In particular, do you model them in the type system and make all your function types that much more complicated? It makes most functions incompatible without glue code.

The most obvious one is integer overflow where a common solution is "don't model it and hope it doesn't happen." Switching to bignums moves the issue to performance where large inputs can cause the program to hang or run out of memory.

Performance and memory usage are never modelled in the type system, which implies that functions with vastly different performance are interchangeable. But we rely on this to be able to improve performance; it's actually better unspecified.

Cracking down on side effects means that in some languages you need to change function signatures to add a log statement, or you can't easily swap in a remote procedure call for a local one. Checked exceptions in Java are an example of how fine-grained tracking of effects helps you paint yourself in a corner where there is rampant cheating out of necessity.

I sometimes wonder if maybe languages like Rust should have every function implicitly return a Result, just so you can report an error later if you need to. Everything is partial, or if not, maybe someday it will be?

But there are languages where any field access can be replaced with an arbitrary function call and that seems bad, so it's probably impractical.

> Performance and memory usage are never modelled in the type system

There's no need tho? If you have types they do the same thing but with different performance guarantees, you can use an interface + sub classes to create your own performance aware types. Same with memory.

> Cracking down on side effects means that in some languages you need to change function signatures to add a log statement

That's an implementation shortcoming. Java isn't forcing you to do this.

> Checked exceptions in Java are an example of how fine-grained tracking of effects helps you paint yourself in a corner where there is rampant cheating out of necessity.

At some level, you have to limit your set or exceptions or error codes. Exceptions from arbitrary code that you otherwise won't be catchable. I think return status/error is much better - that forces all methods in the call stack to think more about the errors that underlying methods with throw and what they will bubble up/handle. It's more work tho.

We use type systems to find bugs when dependencies are upgraded, and performance not being part of the contract between modules means that performance degradation won’t be caught by the type system.

You can deal with it in other ways like running benchmarks often, but I hope you can see why it might be nice in principle if such implicit contracts were made explicit and checked by the compiler? For example, it might make hard realtime systems easier to build and upgrade if there were some formal way of reasoning about deadlines. I haven’t heard of it ever being made practical, though.

Also, I was thinking of Haskell rather than Java as a language where adding logging would change a function’s type signature.

There’s a basic difference between functions that can fail (returning an error) and those that are considered to always succeed (so no error) which I think is well-captured by a type system, whether you do it like Go or Rust or functional languages. If there is any kind of error then you can catch it without distinguishing between them. The same could be done using exceptions too.

The problem with Java is that they tried to distinguish further by what kind of error can be thrown, and this sort of turned into a bad effect system. There are methods that throw IOException and can do I/O and others that throw SQLException so they can talk to a SQL database, and, uh, don’t those categories overlap? And isn’t this exposing implementation details? Why should the caller care whether you use a SQL database or not?

I suspect more principled effect systems might end up having similar problems with functions being inflexibly incompatible due to having different effects, as described in What Color Is Your Function for the sync versus async distinction.

This seems to be the salient part of the article:

"You can make partial functions rigorous by defining them to be relations rather than functions. A relation between sets A and B is a subset of their Cartesian product A × B. A function is a relation such that for every a in A there exists a unique pair (a, b) in the relation. A partial function is a relation in which for every a in A there is at most one pair (a, b) in the relation."

Does this equate with a partial function being one-to-one and onto? [0]

[0] See https://www.math.auckland.ac.nz/class255/08s1/04s2/week5.pdf

This definition of a partial means that not it may be the case that not every element of A gets mapped to an element of B. This is not related to being one-to-one or being onto. In math a function from A to B means each element of A gets mapped to an element of B. With a partial function we allow the possibility that some a in A is not mapped to an element of B. In mathematical language we’d say that a partial function from A to B is a function to B with domain a subset of A. This can be made more rigorous and precise but I don’t feel like writing out the nuance involved.

It does not imply one to one or onto.

Unique pair (a, b) only implies for any a, the corresponding b is unambiguous.

There could easily be (a1, b) and (a2, b), thus not one to one, and there could easily be a b1 such that there is no corresponding A, thus not onto.

> Mathematicians informally speak of functions not being defined everywhere in their domain even though it would be more accurate to say that the domain excludes certain points. This kind of talk is fine among friends where there’s an implicit understanding of what detail is being left out and the trust that the details will be made more explicit when necessary. In a more hostile environment, like Twitter, pedants will gleefully pounce on such lapses in rigor.

While not intended as humor, it seems to me that Mr. Cook transformed the topic of his post from the software to the social setting.

Isn't "implicit understanding" the heart of the matter?

That's... not my understanding of partial functions.

I thought partial functions are functions where you don't supply all the arguments, so the return value is a new function that is ready to accept the missing arguments.

```pseudocode

add(1, 2) > 3

addtwo = add(2)

addtwo(3) > 5 ```

I'm certainly wrong because John D. Cook uses a lot of big words that I don't understand. CONFUSING

That's called Currying. The Add function isn't partial, it has been partially applied, so its the application of the function that maybe called partial.

Different communities using the same word to mean different things is a problem. Especially so, if one isn't aware of it. Another overly abused and overloaded word is functor

> That's called Currying.

Actually no. Currying is converting one function with multiple arguments to a series of functions with one each.

Partial application is supplying some of those arguments and getting back a series of functions that take more arguments.

So, currying = f(x,y,z) -> f'(x)(y)(z)

While partial application = f(x)(y)(z) + x and y being supplied -> f'(z)

> Actually no. Currying is converting one function with multiple arguments to a series of functions with one each

It looked to me that exactly what he was doing, turning the function Add that takes to arguments to a series of two functions that takes one

It seems I misinterpreted your comment then. I thought you were talking about the applying part as currying, which is really common. So I kinda short circuited my reasoning and instantly went for the UMM AKTSCHUALLY.

"Partial functions" as used in the article is a pure mathematics term. "partial application" is what I'd call your example.

I mean he explains what partial functions in his context are in the very first paragraph, not sure how that can be any less confusing!

Well, you do not seem to know all of the meanings of the word 'partial functions'. If one types in 'partial function' in google one can see both the meaning 'partial function' that you have in mind and the meaning of 'partial function' that the article talks about on the first result page. In fact, the 'partial function' of the article appears as the first result. 'CONFUSING' says more about you than about the article.

Off-topic: if you want to post a block of code here, I think your best bet is to indent it with four spaces, instead of using code fences (```).

Ah! Partial application != partial functions. Thanks all!

Reply on news.ycombinator.com