Equatable functions - Githubissues

So, I'm currently doing a little work on equatable functions. I thought I'd jot down a few notes here about motivation and approach.

I should say that I do understand that equatable functions are impossible. That's why they are interesting! No, really, I understand that they are actually impossible.

But I should start with motivation. In the Elm libraries, there are a variety of places, particularly the virtual DOM, where one wants to use a certain kind of laziness. You have a function which you only want to calculate if necessary -- you've got the answer from the previous round, and perhaps it hasn't changed -- perhaps it's the same input, and the same function. Hence, you want to know whether it's the same function!

So, it's not quite like Data.Lazy, because (by itself) Data.Lazy just defers the computation. You can't compare the Data.Lazy to a previous Data.Lazy (except by forcing the computation, which would defeat the purpose).

It's also not quite like memoization, since you only need to remember the most recent application of the function. Also, there are two functions involved here -- the function from the previous round and the function in this round -- and you don't know (without help) whether they are in fact the same function.

Now, the way that Elm deals with this need, in a couple of places, is via reference equality -- that is, it checks whether we're literally dealing with the very same function. One could do this in Purescript as well, of course. However, this leaves us, at least in theory, vulnerable to certain kinds of compiler optimizations. (That is, at least in theory, what we thought would be two references to the very same function might not be). Furthermore, it limits the ways in which we can construct the relevant function -- it really must be the very same function, and thus cannot be returned from another function (which creates a new function each time).

So, can we do better than reference equality? What would that look like?

My main idea is to have a type -- say, EqFn -- which represents a normal function lifted into a context that remembers something about how the function came to be.

Now, to go from Function -> EqFn, one would attach a unique ID to the function. This is basically equivalent to reference equality, but it's all we can do in the case where we're entering the system ... that is, where we don't know anything about how the function was made. One would need to document that, for best results, you should start with functions that are defined at "top-level" -- that is, which are "primitive" functions in some sense -- that is, functions not returned by other functions. AFAIK, there is no way in the type system to insist on that, so it would just be a matter of documentation.

By itself, that is really not much better than reference equality -- we just have a unique ID for the comparison, which is basically equivalent to reference equality. The only advantage so far is that we can arrange matters so that we're not vulnerable to certain kinds of compiler optimization.

However, once we're in the world of EqFn, we can do some interesting things. For instance, we can define a way of composing two EqFn -- that is, the <<< operator -- so that we remember which primitive functions were composed. Then, we can actually compare two EqFn which are the results of composition, even if the composition occurred separately (that is, the two resulting functions are not the very same function).

I've got an initial version of this checked in, with some tests:

https://github.com/rgrempel/purescript-elm/tree/master/src/Data/Function https://github.com/rgrempel/purescript-elm/blob/master/test/Data/Function/Equatable.purs

Now, that implementation turns out to be too simple in some ways ... I'm working on changes that accommodate additional kinds of manipulation of the EqFn. (In particular, the List Int ends up being too simple a structure for the tag). But it gets across the general idea.

I did Google around a bit, and didn't find anything that was quite like this. Which, of course, may mean that it's very badly misconceived! But, it's been interesting so far.

pselm / signals

Equatable functions #12