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
Times are displayed in time zone: (GMT+09:00) Osaka, Sapporo, Tokyo change

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