Thursday, July 3, 2014

Generic higher-order functions and overloads

Let's say we have some type named Spam, and a function validate of type Spam->bool that tells you whether a Spam is valid, and a Spam[] array, and we want to find all the invalid values.

We could of course write a loop, but that's silly; the reason filter exists is to make code like this simpler and more readable. But our predicate does the opposite of what we want, so how can we use filter?

We could write a new inline function that just reverses the sense of the predicate. That works in any language; here it is in Python, Haskell, and Swift:

    filter(lambda x: not validate(x), spam)
    filter (\x -> !validate(x)) spam
    filter(spam) { !validate($0) }

But this can get pretty tedious to write and read, and going through an extra closure for each element could have a performance impact.

Python solves this by identifying a few special cases that come up often, like this one, and writing special functions for those cases, in this case itertools.filterfalse:

    filterfalse(validate, spam)

Haskell, on the other hand, just provides tools to transform functions into different functions. In this case, you just compose the not function with your predicate:

    filter (not . validate) spam

If you're doing this a lot, you can use operator sectioning to define a negate function:

    negate = (not .)
    filter (negate validate) spam

For that matter, if you really wanted a filterfalse function, it's just:

    filterfalse = filter . negate

If that doesn't make any sense, well, that's my fault; I haven't explained that Haskell functions are curried. This means that a function (A, B)->T is the same thing as a function A->(B->T). So, filter doesn't take a predicate and a list and return a list; it takes a predicate and returns a partially-evaluated function that then takes a list and returns a list. So composing it with negate gives you a function that takes a predicate, negates it, and returns a partially-evaluated function that etc.

Anyway, even ignoring that last part (which isn't going to apply to Swift), the Haskell solution is clearly a lot more flexible and powerful. Could we do the same thing in Swift?

Well, there is no compose operator—but, much like Haskell, you can define custom operators out of any combination of the symbols /=-+*%<>!&|^.~ that doesn't already mean something. Unfortunately, a solitary dot already means something, but a double dot, .., is available. So, let's do that:

    operator infix .. {}

    func .. <T, U, V> (left: U->V, right: T->U) -> (T->V) {
        return { left(right($0)) }

So far, so good. So, now we can do this, right?

    filter(spam, ! .. validate)


The first problem is that, while operator functions can be named by their symbols, the parser apparently can't handle two operators in a row—that is, you can't pass the ! function to an operator, or you'll get this string of errors:

    error: unary operator cannot be separated from its operand
    error: unary operator cannot be separated from its operand
    error: '..' is not a prefix unary operator

But we can get past that by giving the parser a little help:

    filter(spam, (!) .. validate)

But that doesn't work either:

    error: could not find an overload for '..' that accepts the supplied arguments

You can check the types; { !$0 } is Bool->Bool, and validate is Spam->Bool, so T is Spam, U is Bool, V is Bool, everything should work. But something is going wrong, and it's not entirely clear what. Can the inference engine not infer this type? Or is it the parser again? Let's try throwing in some more parens:

    filter(spam, ((!) .. validate))

That compiles. So… maybe comma is actually handled as an operator, even though the docs don't say so and it doesn't appear in the stdlib operators, and the comma operator has higher precedence than default custom operators, even though that's silly? Let's change our operator definition and see:

    operator infix .. { precedence 1 }

And now it compiles without the parens. So… I guess that was the issue.

OK, so we can compose the negation operator with a function and do things the Haskell way, rather than the Python way. Cool.

The next example after composing not in many Haskell tutorials is composing reverse and sort. Although Haskell has parametric types instead of generics, the idea is roughly similar. Both functions take a list of elements of any type T and return a list of elements of type T, so their composition does the same.

In Swift, sort takes an Array of any Comparable subtype T and returns an Array of T; reverse takes any Collection whose associated IndexType is at least BidirectionalIndex and returns a custom view struct. Since an Array<T> is a Collection with IndexType Integer (which is a subtype of BidirectionalIndex), everything should work. So, let's try it:

    desort = reverse .. sort


    error: could not find an overload for 'sort' that accepts the supplied arguments

The problem isn't that the types are incompatible:

    let a = [0, 3, 1, 2]
    let b = reverse(sort(a))

For once, the error message is actually helpful. The problem is that sort is not actually a generic function, it's an overload of two separate generic functions. One takes an Array of any Comparable subtype T, the other takes an Array of any type T plus a predicate from (T, T)->Bool.

The frustrating thing is that the types of both overloads can be composed with reverse; (T[], (T, T)->Bool)->T[] is just as compatible with with (C : Collection where C.IndexType : BidirectionalIndex)->ReverseView<C> as T[]->T[] is.

In some cases, this isn't a problem. For example, you can map sort over an array. Why? Because map actually applies its function argument (as opposed to returning a function that will apply it later), which means the type of the arguments is known at the time you call map (rather than being a generic type to be resolved at the time you call the returned function); the Element type associated with the Sequence or Collection is the only argument to sort, therefore the one-parameter sort overload is selected.

So, generic higher-order functions that don't actually apply their function arguments immediately do not play well with overloads in Swift. Which sucks, because those are two powerful features that you'd frequently want to use in the same place (see my previous post about how overloads allow functions like map to return a lazy Collection when possible, a one-shot Generator when not), but instead, you have to choose one or the other. The Swift stdlib seems to have gone with the overload feature. Which means the Haskell-like solution of providing a compose operator, a flip function, etc. isn't going to work in Swift, and we'll have to go with the weaker option of explicitly providing functions like filterfalse for each important-enough special case.

One way Swift could resolve this is to give an overload set a disjunctive type made up of the types of each overload. So, the two overloads shown below would combine into the single type:

    func sort<T : Comparable>(array: T[]) -> T[]
    func sort<T>(array: T[], pred: (T, T) -> Bool) -> T[]

    func sort<T: Comparable | U>((T[] | (U[], (U, U) -> Bool)) -> (T[] | U[])

Would that type be compatible with reverse? Yes; both T[] and U[] match C : Collection where C.IndexType : BidirectionalIndex. So, if we define desort = reverse .. sort, its type ends up as:

    func desort<T: Comparable | U>((T[] | (U[], (U, U) -> Bool)) -> 
        (ReverseView<T[]> | ReverseView<U[]>)

Then, inside desort, whether it got one parameter or two, it's just passing that off to sort, which has to handle overload resolution normally, so everything should work.

No comments:

Post a Comment