Tournament sort

import Data.Tree

nodify :: [t0] -> [Tree t0]
{-  Adapted from `LISTIFY!` in the Stepanov and Kershenbaum report
    Input:
        `alist`; a list of items to be sorted
    Output:
        a forest of trivial trees, such that each tree has one element of `alist` as its `rootLabel` -}
nodify alist = map ( \u -> Node {rootLabel=u, subForest=[]} ) alist

promote :: Tree t0 -> Tree t0 -> Tree t0
{-  Adapted from `GRAB!` in the Stepanov and Kershenbaum report
    Input:
        `loser`, `winner`; trees
    Output:
        a tree whose root is the root of `winner` and whose children are:
            * `loser`,
            * and all the children of `winner` -}
promote winner loser = Node {
    rootLabel = rootLabel winner,
    subForest = loser : subForest winner}

playGame :: (t0 -> t0 -> Bool) -> Tree t0 -> Tree t0 -> Tree t0
{-  Adapted from `TOURNAMENT-PLAY!` in the Stepanov and Kershenbaum report
    Input:
       `inc`; a two-argument predicate that returns `True` if its arguments are in increasing order
       `tree1`, `tree2`; trees whose roots will be referred to as `r1` and `r2`
    Output:
        `promote winner loser` where `winner` is the tree among `tree1` and `tree2` with the *lesser* root-}
playGame inc tree1 tree2
    | i == True  = promote tree1 tree2
    | otherwise  = promote tree2 tree1
    where
        r1 = rootLabel tree1
        r2 = rootLabel tree2
        i = inc r1 r2

playRound :: (t0 -> t0 -> Bool) -> Forest t0 -> Forest t0 -> Forest t0
{-  Adapted from `TOURNAMENT-ROUND!` in the Stepanov and Kershenbaum report
    Input:
        `inc`; a two-argument predicate that returns `True` if its arguments are given in increasing order
        `to_do`; a forest of trees that have not yet competed in round
        `done`; a forest of trees that have won in round
    Output:
        `winners`; a forest containing promoted versions of the trees that won their games -}
playRound inc [] done = done
playRound inc [tree] done = tree:done
playRound inc (tree1:tree2:trees) done = playRound inc trees (winner:done)
    where winner = playGame inc tree1 tree2

playTournament :: (t0 -> t0 -> Bool) -> Forest t0 -> Tree t0
{-  Adapted from `TOURNAMENT!` in the Stepanov and Kershenbaum report
    Input:
        `inc`; a two-argument predicate that returns `True` if its arguments are given in increasing order
        `trees`; a forest of trees
    Output:
        `winner`; the last promoted tree -}
playTournament inc [tree] = tree
playTournament inc trees = playTournament inc (playRound inc trees [])

tournamentSortSimple :: (t0 -> t0 -> Bool) -> Forest t0 -> [t0]
{-  Adapted from `TOURNAMENT-SORT!` in the Stepanov and Kershenbaum report, but not the final function because it still takes a forest, not a list of elements, as input.
    Input:
        `inc`; a two-argument predicate that returns `True` if its arguments are given in increasing order
        `trees`; a forest of trees
    Output:
        `sortedTrees`; `trees`, but in increasing order by root
-}
tournamentSortSimple inc [] = []
tournamentSortSimple inc trees = r : tournamentSortSimple inc sf
    where
        len = length trees
        winner = playTournament inc trees
        r = rootLabel winner
        sf = subForest winner

tournamentSort :: (t0 -> t0 -> Bool) -> [t0] -> [t0]
{-  The complete sort.
    Input:
        `inc`; a two-argument predicate that returns `True` if its arguments are given in increasing order
        `alist`; an unsorted list
    Output:
        sorted version of `alist`
-}
tournamentSort inc alist = tournamentSortSimple inc (nodify alist)

inc1 :: Ord t0 => t0 -> t0 -> Bool
-- The two-argument predicate mentioned repeatedly until this point. Perhaps we could have simply used `<` without requiring an additional argument, but it's nice to be able to write a predicate to compare whatever we want without necessarily defining an entire order structure.
inc1 a b = a < b

testList = [-0.202669, 0.969870, 0.142410, -0.685051, 0.487489, -0.339971, 0.832568, 0.00510796, -0.822352, 0.350187, -0.477273, 0.695266]
sortedList = tournamentSort inc1 testList

main = print sortedList