Ciencias de la Computación FAMAF

import Array

data Cola e = Vacia
              | Encolar (Cola e) e
              deriving Show


es_vacia :: Cola e -> Bool
primero :: Cola e -> e      -- se aplica a colas no vacías
decolar :: Cola e -> Cola e -- se aplica a colas no vacías

es_vacia Vacia = True
es_vacia (Encolar q e) = False

primero (Encolar Vacia e) = e
primero (Encolar q e) = primero q

decolar (Encolar Vacia e) = Vacia
decolar (Encolar q e) = Encolar (decolar q) e

-- Ejemplos

q0 = Vacia :: Cola Int
q1 = Encolar q0 1
q2 = Encolar q1 2
q3 = Encolar q2 3
q4 = Encolar q3 4

decolar_todo :: Cola e -> [e]
decolar_todo q = if es_vacia q then [] else primero q : decolar_todo (decolar q)

arreglo_ini :: Array Int (Cola Int)
arreglo_ini = array (0,9) [(i,Vacia) | i<- [0..9]]

radix_sort :: [Int] -> [Int]
radix_sort as = radix_fase 3 (radix_fase 2 (radix_fase 1 as))

radix_fase :: Int -> [Int] -> [Int]
radix_fase i as = juntar (clasificar i as arreglo_ini)

clasificar :: Int -> [Int] -> Array Int (Cola Int) -> Array Int (Cola Int)
clasificar i [] a = a
clasificar i (x:xs) a = clasificar i xs (modificar_arreglo a k (`Encolar` x))
                      where k = iesimo_digito i x

modificar_arreglo :: Ix a => Array a b -> a -> (b -> b) -> Array a b
modificar_arreglo a i f = a // [(i,f (a!i))]

iesimo_digito :: Int -> Int -> Int
iesimo_digito i x = (x `div` 10^(i-1)) `mod` 10 

juntar :: Array Int (Cola Int) -> [Int]
juntar a = juntar_rec [0..9]
         where juntar_rec [] = []
               juntar_rec (i:is) = decolar_todo (a!i) ++ juntar_rec is