0votos

concatenacion de pilas ordenadas en Haskell

por josejuan hace 3 años

Usando lazy es recorrer las pilas (que son listas por lazy). Se hace una versión directa usando listas y otra usando sólo operaciones PÛSH/POP de pilas.

me piden concatenar dos pilas (ya ordenadas ) ,es decir, unir dos pilas en una pila nueva con el objetivo de que los elementos que estuvieron ordenados queden en la pila nueva ordenada.la pila resultante tiene que tener todos sus elementos ordenados.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import Data.Maybe 
 
-- Usando la pila del propio compilador 
concatSort :: Ord a => [a] -> [a] -> [a] 
concatSort = s 
    where s []       []       = []                          -- no hay nada que ordenar 
          s xs@(_:_) []       = xs                          -- sólo queda de la primera 
          s []       ys@(_:_) = ys                          -- sólo queda de la segunda 
          s (x:xs)   (y:ys) | x < y     = x: s xs (y:ys)    -- apilamos de la primera y ordenamos el resto 
                            | otherwise = y: s (x:xs) ys    -- apilamos de la segunda y ordenamos el resto 
 
-- Usando explícitamente dos pilas 
concatStacks :: Ord a => [a] -> [a] -> [a] 
concatStacks = s 
    where s a b = case (pop a, pop b) of 
                    (     Nothing,      Nothing) -> [] 
                    (Just (x, xs),      Nothing) -> push x xs 
                    (     Nothing, Just (y, ys)) -> push y ys 
                    (Just (x, xs), Just (y, ys)) -> if x < y then push x $ s xs $ push y ys 
                                                             else push y $ s ys $ push x xs 
 
-- Operaciones de pila 
push :: a -> [a] -> [a] 
push x xs = x: xs 
 
pop :: [a] -> Maybe (a, [a]) 
pop (x:xs) = Just (x, xs) 
pop _      = Nothing 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.