Typelevel quicksort in Scala | Hacker News Reader

Typelevel quicksort in Scala

jto.github.io

60 pointslelf33 comments

[warning: ignorant musing of someone who doesn't know Scala below]

This makes me wonder if 'values' can be though of as just subtypes of their types. '5' extends 'Number', say. Is this how it's interpreted in the fully-functional paradigm?

If you have

def fn(x: Int) : Int

then 'Int' is the type of all Ints, and you have to provide a specific int - which is a subtype of Int, but you could imagine there being a subtype between 'Int' and '5', like:

5 <: intermediateType <: Int

So in order to 'invoke' a function you have to provide a subtype that reduces it to one value, at the level of 5, not just any subtype of int. Meaning that something about '5' makes it a special kind of subtype that can actually be used to execute the function. Maybe that's what we mean by 'value'. I don't know.

I do find the idea that fn(5) is a subtype of fn(x: Int) to be cute.

And that

def foo(x: Int): Int = fn(x)

has the 'subtype'

foo(5): fn(5)

seems suggestive.

There's some significant sense to what you're talking about, so I'll share some pointers into deeper waters.

The idea of a value being a type is the nature of "dependently typed" languages. However, they do it the other way around: types are merely values. This is very similar to what you're saying except DT languages would not have that

    5 : 5

Instead, we introduce the idea of a singleton type. It works like this: for any type A and any value (x : A), we have a type (Sing A x) with exactly one value, (TheSing x : Sing A x).

The other thing to keep in mind is that subtyping is kind of a rocky place to lay your type semantics. This is rough because most people are used to subtyping in their types. Instead, we note that whenever we have that (A :> B) then we have a function (A -> B) which is injective (really, an "epimorphism"). This broaden's our view to consider any injective function between types instead of merely some subtyping relation. Immediately it ought to be clear that (a) this is intractable automatically and (b) it's far more rich. Then it turns out that subtyping itself is fairly intractable (which subtypes are the right ones? there are many types intermediate between (Sing Integer 5) and (Integer)).

So throw away automatic subsumption and require explicit coercions. This is workable and indeed in use today.

It seems that you can either fight subtyping (by avoiding it) or embrace it; e.g. with pure subtype system:

http://people.tamu.edu/~hiraditya/index_files/ProgLang_Prese...

You do exchange a typing judgment for a subtyping one.

I feel like we haven't really looked at subtyping enough. It might not be so hard as it is different, that our existing type systems simply aren't suited to it but we could come up with subtype systems that are.

This is really interesting, thanks.

For a bit of theoretical background, try http://www.cl.cam.ac.uk/teaching/1415/Types/types.notes.pdf (it's fairly easy reading). I'm not sure I quite understand what you're saying completely, but typically we distinguish types from values because we otherwise find it very difficult to write a performant typing algorithm.

Personally, I try to avoid subtyping where possible; I usually end up getting weird contradictions.

You may be interested in how Typed Racket does types.

http://docs.racket-lang.org/ts-reference/type-ref.html

What sort of support does Scala have going forward? My understanding is that although there are a lot of scala users, a lot of major corporate users have backed away from it, ex. LinkedIn, Twitter, etc, because of fundamental issues with the language.

Never heard of Twitter abandoning Scala. They actually seem committed. LinkedIn changes technology often. But that does not have to mean much. It is still well used and on surveys immediately after the regulars such as java, python, c++,c#, js.

As someone who's recently been jobhunting, Scala feels more popular than ever. It may no longer be as hyped as it was (which is probably better for everyone), but it's still growing.

And really there is no alternative - once you've used higher-kinded types there's no going back. Some organizations make the switch to Haskell, but that's not an option in many environments. Other than that, if you want higher-kinded types there's nothing that's remotely as mature as Scala out there.

I can't speak to "fundamental issues with the language" because I haven't found any.

The problem with Scala is that architects can and sometimes will get giddy and create monsters. Scala is not like C++ where some features are dangerous, but Scala has features that should be used with caution. The amount of times where defining a partially applied higher-order function is the best way to solve a problem is nonzero, but still really really low. So you let a team of giddy developers eager to learn and apply new concepts loose and soon you have a monster of a code base.

> The amount of times where defining a partially applied higher-order function is the best way to solve a problem is nonzero, but still really really low

I disagree. Once you learn to use partially applied higher-order functions, they end up being useful everywhere. I'm using them right now in Scala for my day job, and my code is not particularly fancy.

> The problem with Scala is that architects can and sometimes will get giddy and create monsters.

> The amount of times where defining a partially applied higher-order function is the best way to solve a problem is nonzero, but still really really low.

I was with you until this. Using partial application doesn't create monsters, and in fact is rather easy to follow and understand (assuming you know what partial application is, of course).

There are however, features of Scala that can be abused to create monsters, the most obvious of which is implicit conversions. An extremely useful feature, but can cause a mess if you're not careful. And even with those, it's still entirely static, and your IDE can highlight which ones happened where, as opposed to something like Ruby, where you can update classes at runtime.

> The amount of times where defining a partially applied higher-order function is the best way to solve a problem is nonzero, but still really really low.

Not sure about Scala, but I find partially applied higher order functions to frequently be the best choice in Haskell code.

It's called code review. Unless you have stupid time constraints, you don't let that happen.

Scala is like C++ where some features are dangerous. We've had significant problems with parts of the standard library and had to resort to banning them and writing our own alternatives.

Which portions of the standard library?

Trying to perform a sequential operation on a parallel collection will not go well, but other than that I haven't seen anything.

Given that higher-kinded types are not included by default in Scala 2.11 (e.g. they're considered "advanced" and optional), I'm not sure that's true.

That was a controversial decision; typesafe is not always entirely aligned with the wider community.

And you're not exactly contradicting me. They are an "advanced" feature partly because they're not found in (many) other languages.

> And really there is no alternative - once you've used higher-kinded types there's no going back.

Do companies that have adopted Scala really value higher-kinded typing that much?

Higher-kinded types themselves, not necessarily, but the abstractions they afford are, once you've gotten used to them, a huge time saver.

I've gotten used to handling concurrency as a monad, for example, and honestly dread the time when I have to manually deal with manual synchronisation again.

Companies are made of people, and the people writing the code certainly do, IME. (In some companies that will have little bearing on the company's decisionmaking, but I view that as an indictment of those companies' processes). It's not something that immediately jumps out, but having written code for a while with higher-kinded types available, it would be horrible to have to expand that out into cases.

It just seems weird that this feature would stand out when compared to everything else Scala has to offer.

There are plenty of features in Scala that I couldn't live without, but most of them are features that I could find in other languages (e.g. Ceylon, F#). Higher-kinded types are the big "blocker" that really keeps me Scala-only.

Dunno, I know plenty of major corporate users that are adopting Scala, I bet I can name two adopters for each one you know that backed away from it... And not "we use it in this dark corner where nobody cares", more like "is the backbone of our new business"

I keep hearing this, but the fact is that both companies continue to use Scala for core functions. There are plenty of Scala jobs out there.

I'm currently on the job market after spending two years working with Scala. There's definitely no shortage of companies out there hiring Scala talent. In the last two days I've been contact by at least five companies using Scala. Over the course of my job search it's been many more. Just last week I found out that Verizon has at least 300 Scala developers on staff.

An added benefit: due to the scarcity, lots of Scala shops are open to remote developers. I abhor the idea of moving back to the Bay Area so that's important to me.

Do note that the article is pretty far away from real-world, day to day use of Scala in mainstream programming. The author is merely having fun with types.

Having said that, what evidence do you have that Twitter is backing away from Scala? What are they supposed to be replacing it with? My own experience is that mainstream jobs in my country are very slowly and timidly starting to adopt Scala, and only in the most controlled fashion, as "just a better Java".

This is cool and clever. But if it doesn't sort in O(1) memory, it's not quicksort. With the lambda calculus lacking a concept of place, it's always going to be tough ensure sorting in place...or randomized pivots as in Hoare's algorithm.

Quicksort is O(log n) space, not O(1).

And if you're implementing pure Quicksort you have to make sure to recurse on the smaller partition first, otherwise you're using O(n) space in the worst case.

You don't have to do this if you're already using a hybrid sort to prevent Quicksort's worst case, like introsort or (shameless self promotion) pdqsort (https://github.com/orlp/pdqsort).

>you have to make sure to recurse on the smaller partition first, otherwise you're using O(n) space in the worst case

I haven't run the math, but I don't believe introsort fixes this. It's a constant-factor optimization.

Introsort switches to heapsort if the recursion depth becomes too big to limit runtime to O(n log n), which indirectly also limits space to O(log n).

Reply on news.ycombinator.com