¡Esta es una revisión vieja del documento!
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