Write a Blog >>
ICFP 2016
Sun 18 - Sat 24 September 2016 Nara, Japan
Mon 19 Sep 2016 17:50 - 18:15 at Noh Theater - Session 4 Chair(s): Tom Schrijvers

The combination of non-determinism and sorting is mostly associated with permutation sort, a sorting algorithm that is not very useful for sorting and has an awful running time.
In this paper we look at the combination of non-determinism and sorting in a different light: given a sorting function, we apply it to a non-deterministic predicate to gain a function that enumerates permutations of the input list. We get to the bottom of necessary properties of the sorting algorithms and predicates in play as well as discuss variations of the modelled non-determinism.
On top of that, we formulate and prove a theorem stating that no matter which sorting function we use, the corresponding permutation
function enumerates all permutations of the input list. We use free theorems, which are derived from the type of a function
alone, to prove the statement.

Mon 19 Sep

icfp-2016-papers
17:00 - 18:15: Research Papers - Session 4 at Noh Theater
Chair(s): Tom SchrijversKU Leuven
icfp-2016-papers17:00 - 17:25
Talk
Kotaro TakedaUniversity of Tokyo, Japan, Naoki KobayashiUniversity of Tokyo, Japan, Kazuya YaguchiTohoku University, Japan, Ayumi ShinoharaTohoku University, Japan
DOI
icfp-2016-papers17:25 - 17:50
Talk
Shin-Cheng MuAcademia Sinica, Taiwan, Yu-Hsi ChiangNational Taiwan University, Taiwan, Yu-Han LyuDartmouth College, USA
DOI
icfp-2016-papers17:50 - 18:15
Talk
Jan ChristiansenFlensburg University of Applied Sciences, Germany, Nikita DanilenkoUniversity of Kiel, Germany, Sandra DylusUniversity of Kiel, Germany
DOI