Hacker News Reader

Comment by chenglou | Hacker News Reader

This is pretty neat! https://github.com/agraef/pure-lang/wiki/Rewriting#construct...:

> As a bonus, you also get "constructors with equations" for free. E.g., suppose that we want lists to automagically stay sorted and eliminate duplicates. In Pure we can do this by simply adding the following equations for the : constructor:

  > x:y:xs = y:x:xs if x>y; x:y:xs = x:xs if x==y;
  > [13,7,9,7,1]+[1,9,7,5];
  [1,5,7,9,13]

(The point about this global override is addressed later. The rewriting can be lexically scoped.)

View on HN

Isn't this basically bubble sort?

If you build such a list by consing new elements to the front, then it's insertion sort. If you build the list from a balanced binary tree it's merge sort.

---

One important difference between this and quotient-inductive types is that there are examples of "types with equations" which cannot be expressed as a rewriting system, e.g., free groups.

It's a still a cool feature to have this built into the language.

> If you build the list from a balanced binary tree it's merge sort.

But in the example, the list is built by adding two lists. This means that in the example, it uses insertion sort which like bubble sort is O(n^2).

You're right and looking at the example again I was completely wrong (shouldn't post without coffee). You can implement merging by writing append (+) in the correct way. As written, the code will always insert a new element every time there is a cons (:).

One way of getting better performance "by default" is to construct lists with constructors for empty list, singletons and append and then adding equations to ensure that the resulting binary tree is balanced.

No, the sources must be pre sorted for this to work. What this does is merge two lists of dynamic size like a set like a zipper.

I.e., Mergesort?

Eliminates duplicates too

Reply on news.ycombinator.com