-- |
-- Module      : BusquedaEnEscalada
-- Description : El patrón de búsqueda en escalada.
-- License     : Creative Commons
-- Maintainer  : José A. Alonso
-- 
-- = El patrón de búsqueda en escalada
-- 
-- Este módulo contiene la definición del patrón de búsqueda en escalada
-- estudiado en el <http://bit.ly/1LIx3CJ tema 15> del curso. 
--
-- Además, en el tema se incluye como de casos de aplicación del patrón 
--
-- * <http://bit.ly/1LIx4GQ el problema del cambio de monedas> y
-- * <http://bit.ly/1LIx5ui el algoritmo de Prim del mínimo árbol de
-- expansión>. 

module I1M.BusquedaEnEscalada (buscaEscalada) where

-- ---------------------------------------------------------------------
-- Importaciones                                                      --
-- ---------------------------------------------------------------------

import I1M.ColaDePrioridad

-- ---------------------------------------------------------------------
-- El patrón de búsqueda en escalada                                  --
-- ---------------------------------------------------------------------

-- | (buscaEscalada s o e) es la lista de soluciones del problema de espacio de
-- estado definido por la función sucesores (s), el objetivo (o) y el
-- estado inicial (e), obtenidas buscando por escalada.
buscaEscalada :: Ord nodo => 
                 (nodo -> [nodo])   -- sucesores
                 -> (nodo -> Bool)  -- es final
                 -> nodo            -- nodo actual
                 -> [nodo]          -- soluciones
buscaEscalada :: forall nodo.
Ord nodo =>
(nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo]
buscaEscalada nodo -> [nodo]
sucesores nodo -> Bool
esFinal nodo
x = CPrioridad nodo -> [nodo]
busca' (nodo -> CPrioridad nodo -> CPrioridad nodo
forall a. Ord a => a -> CPrioridad a -> CPrioridad a
inserta nodo
x CPrioridad nodo
forall a. Ord a => CPrioridad a
vacia) 
    where
      busca' :: CPrioridad nodo -> [nodo]
busca' CPrioridad nodo
c  
        | CPrioridad nodo -> Bool
forall a. Ord a => CPrioridad a -> Bool
esVacia CPrioridad nodo
c           = [] 
        | nodo -> Bool
esFinal (CPrioridad nodo -> nodo
forall a. Ord a => CPrioridad a -> a
primero CPrioridad nodo
c) = [CPrioridad nodo -> nodo
forall a. Ord a => CPrioridad a -> a
primero CPrioridad nodo
c]
        | Bool
otherwise           = 
            CPrioridad nodo -> [nodo]
busca' ((nodo -> CPrioridad nodo -> CPrioridad nodo)
-> CPrioridad nodo -> [nodo] -> CPrioridad nodo
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr nodo -> CPrioridad nodo -> CPrioridad nodo
forall a. Ord a => a -> CPrioridad a -> CPrioridad a
inserta CPrioridad nodo
forall a. Ord a => CPrioridad a
vacia (nodo -> [nodo]
sucesores (CPrioridad nodo -> nodo
forall a. Ord a => CPrioridad a -> a
primero CPrioridad nodo
c)))