-- |
-- Module      : DivideVenceras
-- Description : El patrón "divide y vencerás".
-- License     : Creative Commons
-- Maintainer  : José A. Alonso
-- 
-- = El patrón "divide y vencerás"
-- 
-- La técnica "divide y vencerás" consta de los siguientes pasos:
-- 
-- 1. Dividir el problema en subproblemas menores.
-- 2. Resolver por separado cada uno de los subproblemas; si los
--    subproblemas son complejos, usar la misma técnica recursivamente;
--    si son simples, resolverlos directamente.
-- 3. Combinar todas las soluciones de los subproblemas en una solución
--    simple. 
-- 
-- Este módulo contiene la definición del patrón "divide y vencerás"
-- estudiado en el <http://bit.ly/1IstbhD tema 15> del curso. Además, en
-- el tema se incluye dos casos de aplicación del patrón:   
--
-- * <http://bit.ly/1Istd99 la ordenación por mezcla> y
-- * <http://bit.ly/1Istid7 la ordenación rápida>.

module I1M.DivideVenceras (divideVenceras) where

-- ---------------------------------------------------------------------
-- El patrón de diseño "divide y vencerás"                            --
-- ---------------------------------------------------------------------

-- La técnica "divide y vencerás" consta de los siguientes pasos:
-- 1. Dividir el problema en subproblemas menores.
-- 2. Resolver por separado cada uno de los subproblemas; si los
--    subproblemas son complejos, usar la misma técnica recursivamente;
--    si son simples, resolverlos directamente.
-- 3. Combinar todas las soluciones de los subproblemas en una solución
--    simple. 

-- | (divideVenceras ind resuelve divide combina pbInicial) resuelve el
-- problema pbInicial mediante la técnica de divide y vencerás, donde
-- 
-- * (ind pb) se verifica si el problema pb es indivisible 
-- * (resuelve pb) es la solución del problema indivisible pb
-- * (divide pb) es la lista de subproblemas de pb
-- * (combina pb ss) es la combinación de las soluciones ss de los
--      subproblemas del problema pb.
-- * pbInicial es el problema inicial
divideVenceras ::    
    (p -> Bool)     
    -> (p -> s)        
    -> (p -> [p])      
    -> (p -> [s] -> s) 
    -> p               
    -> s
divideVenceras :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s
divideVenceras p -> Bool
ind p -> s
resuelve p -> [p]
divide p -> [s] -> s
combina = p -> s
dv' where
  dv' :: p -> s
dv' p
pb
    | p -> Bool
ind p
pb    = p -> s
resuelve p
pb
    | Bool
otherwise = p -> [s] -> s
combina p
pb [p -> s
dv' p
sp | p
sp <- p -> [p]
divide p
pb]