\documentclass[10pt,letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\lstnewenvironment{code}{\lstset{language=Haskell,basicstyle=\small}}{}
\author{Alexander Schaap}
\title{Alphabetizer}
\begin{document}

\maketitle

This module sorts a given collection of lines using the ordering specified by the word implementation. 
It then stores the sorted lines into a storage that allows for ordered elements.
Similar to the circular shifter, data does not necessarily need to pass through this module.
However, words need to be compared - whether this can stay on the potentially 'remote' side remains to be seen.
Incrementality is somewhat of an issue, depending on how strictly Parnas' specification is followed.
If the storage containing unordered lines (shifts) is updated, this module can ensure that the ordered storage will contain the newly added lines while maintaining order.
Iterators should be explored as an alternative to indices when sorting.
Another avenue to explore is bringing this module 'closer' to the storage module, possibly even integrating it.

The secret here is the sorting algorithm.

As with circular shifter, Parnas specified this module would produce a collection of indices, which might not be desirable (for example, when using iterators instead).
\begin{code}
{-# LANGUAGE MultiParamTypeClasses, TypeSynonymInstances #-}
module Alphabetizer where

import LineStorage
import Word
import Data.List
import qualified Data.IntMap as IntMap

class Alphabetizer s t r where
  sort_ :: (Word e, Ord e) => (s (t (r e))) -> (s (t (r e)))

compareLines :: (Word e, Ord e) => [e] -> [e] -> Ordering
compareLines [] _ = LT
compareLines _ [] = GT
compareLines (e1:e1s) (e2:e2s)
  | r  ==  EQ = compareLines e1s e2s
  | otherwise = r
  where r = compareTo e1 e2

instance Alphabetizer StorageList StorageList StorageList where
  sort_ (ListStorage s) = ListStorage $ map (ListStorage . sortLS) s
    where sortLS (ListStorage e) = map ListStorage $ sortBy compareLines $ map extr e
          extr (ListStorage l) = l

instance Alphabetizer StorageMap StorageMap StorageMap where
  sort_ s = IntMap.map (toMap . (map toMap) . (sortBy compareLines)) listListsLists
    where toMap = foldl add IntMap.empty
          listListsMaps = IntMap.map IntMap.elems s
          listListsLists = IntMap.map (map IntMap.elems) listListsMaps

\end{code}

\end{document}