Priority Sorter
Priority Sorter
Authors
Augustine Kwong and Ben Daly-Grafstein
What is the problem?
Sorting a to-do list is a tedious task. Not just to-do lists, but priorities in general. When making any decision on discrete items, it would be useful to be able to compare elements only pairwise, and derive an ordering from that. From sorting principles, we can do this using a comparison sort algorithm that queries the user for ordinal rankings as it progresses.
Purpose: User provides a list of todo items in a text file. Running the program prompts the user to decide (pair-wise) which item is more important to complete. The program presents 3 choices for an unknown pair of items:
* Option 1 is more important * Option 2 is more important * Indifferent
After the user answers enough questions, the program writes the sorted list back to a file.
Input: New-line separated .txt file of todo items
Output: New-line separated .txt file of sorted items according to user’s answers
Enough Questions: Assume that comparisons are transitive, thus if A > B and later B > C, then we should implicitly order A > C to minimize the # of comparisons.
What is the something extra?
While it would be possible to require the user to make n^2 comparisons, this becomes more of the chore than a solution for it. Therefore, we've implemented a comparison caching matrix, that propagates implied transitive orderings i.e. if A > B and B > C, then A > C. We also permuted the original list before using a merge-sort. This amortizes the average comparisons needed to n log n.
What did we learn from doing this?
It was very important that we divided the problem into really small manageable pieces. We had to actually think about how to store the comparisons and pass that information down to further comparisons, but also save the information in the "parent nodes" when merging the result. The intermittent IO added another level of complexity that we had to try and understand. Working together on understanding how to work around the IO limitations and slowly iterating a more complex and refined solution helped us better understand how to make Haskell code more readable for each other. Being able to read and re-use each other's code was a challenge at first but became easier as we familiarized ourselves with our styles and documentation.
We think that requiring the intermittent IO input from the user required our solution to be functionally impure. Though Haskell was excellent when it came to expressive code for sorting algorithms, injecting impure processes into this sorting process was a big challenge. We appreciate the way we were forced to think about how different states can be managed via new function calls as opposed to imperative state. We also found the nature of debugging pure functions very rewarding and different. It seems that if you get the code to compile, it generally works! But the problem is deciphering the types underlying your code!