3 ms·
Isn't this basically bubble sort?
by otabdeveloper2 9y ago
Isn't this basically bubble sort?
- cordite 9y agoNo, 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.
- deleted 9y ago[deleted]
- fmap 9y agoIf 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.
- amelius 9y ago> 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).
- fmap 9y agoYou'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.