Typyfying function signatures

Question
1

Is there a way to give function signatures a type with a name?

Example and motive:
Lets look at the strategy pattern from OOP. With functional programming it is much simpler.

def sortMySeq(strategy: Seq[Int] -> Seq[Int], unsorted: Seq[Int]): Seq[Int] = ???

//strategies:
def bubbleSort(unsorted: Seq[Int]): Seq[Int] = ???
def quickSort(unsorted: Seq[Int]): Seq[Int] = ???

//usage
sort(quickSort, mySeq)

Now every function f with the signature Seq[Int] -> Seq[Int] could be passed to the sortMySeq function. Even if it is not a sort function.

I though maybe there is a way to make it typesafe by giving this signature a type with a name. Of course we could do:

trait SortAlgorythm {
     def sort(unsorted: Seq[Int]): Seq[Int]
}

and the sortMySeq function becomes:

def sortMySeq(strategy: SortAlgorythm, unsorted: Seq[Int]): Seq[Int] ???

But that’s the original OOP strategy pattern.

If we could do something like this:

functionType SortAlgorythm: Seq[Int] -> Seq[Int]

Where functionType is a language keyword and SortAlgorythm is the name of the signature than me have to tell that which functions are sorting functions:

def bubbleSort: _SortAlgorythm = ???
def quickSort: _SortAlgorythm = ???

This is nothing more an fictional example syntax.

With this SortAlgorythms and other functions with the same signature like a reverse function could be told apart. Transforming this to the trait/interface version in the background is one way that the compiler can translate it. So maybe this is just syntactic sugar.

Maybe I miss something that already exists and could be used in such a way. If not I would be glad to hear what you think about it and if this could be a useful addition to the language.

2

Since you’re lifting the method (def) to function (passed as argument to sortMySeq) anyway you can do that once, i.e. change def bubbleSort(unsorted: Seq[Int]): Seq[Int] into val bubbleSort: Seq[Int] => Seq[Int] and then you can create ordinary type alias type SortAlgorithm = Seq[Int] => Seq[Int] and use it to type the val: val bubbleSort: SortAlgorithm.

BTW: What’s the problem with strategy pattern? With Scala 2.12+ it can be pretty concise:

trait SortAlgorithm {
  def apply(unsorted: Seq[Int]): Seq[Int]
}

val stdSort: SortAlgorithm =
  unsorted => unsorted.sorted

println(stdSort(Seq(3, 1, 2))) // prints: List(1, 2, 3)

Above solution has the advantage over standard functions (i.e. FunctionN traits) that you can name parameter (unsorted vs something generic in FunctionN traits) and have specific type SortAlgorithm instead of generic FunctionN which is easier to wrongly use (as Function1[Seq[Int], Seq[Int]] doesn’t have to be a sort algorithm).

1 Like
3

There is no severe problem with the strategy pattern. I simply was trying to do it more functional. As we have functions as first class citizens and higher order functions in Scala, I thought that using them for flexible behavior would be a good idea, potentially shorten the code and possibly being useful for other cases, too.

The solution with type aliases is interesting. I see the pros and cons you mentioned. Unfortunately it doesn’t the type safety that I was hoping for.

4

Not sure what kind of type safety you are actually hoping for…

As @tarsa demonstrated, function values can be directly used where single method traits are expected (the method name doesn’t even have to be #apply()), so the “OO style” implementation does not significantly raise the level of “type safety” over the plain type alias - it’s just making the underlying machinery a tad more complicated.

If you want to make clients of your API think really hard about whether the values they pass actually meet the (implicit) constraints, you’ll have to force them to wrap the sort function into a dedicated type, akin to Haskell’s newtype. This could just be a simple (vanilla or case class).

class SortAlgorithm(val sort: Seq[Int] => Seq[Int])

To soften the performance and inconvenience overhead for (un-)boxing, you could use tagged or value types, for example.

However, this still doesn’t keep a client from providing an “illegal” implementation, be it something obviously wrong like #reverse() or just a buggy implementation of a proper sorting algorithm. If you want actual type safety at this level, you’ll have to look elsewhere. :wink:

5

From my experience, absolute shortening of the code isn’t always good. For example if I have a function String => Int and pass it around freely, through multiple levels of methods, through multiple classes, save it in some fields, maps or rich structures then I have hard time figuring out where a particular function value comes from because there’s a lot of String => Int function instances around. If instead I have a separate trait e.g. trait PathElementsCounter { def apply(path: String): Int } then finding where it was created will be much simpler as there are much fewer instances of PathElementsCounter than instances of String => Int. Additionally I can put some very descriptive names in that trait (like PathElementsCounter vs Function1 and path vs v1) and that would help me understand the code.