-- JC 12-3-2001 traducci�n a Haskell, versi�n currificada

module Backtr (backtr, backtr_cont, 
               backtr_prim_sol, backtr_prim_sol_cont) where 

--import Holo

-- versi�n currificada



backtr::
     (tsolucionParcial -> Bool)                      -- EsSolucionFinal?
     -> (tsolucionParcial -> tsolucion)              -- Convertir
     -> (tsolucionParcial -> [tsolucionParcial])     -- Ampliar
     -> (tsolucionParcial -> Bool)                   -- EsValida?
     -> tsolucionParcial                             -- Estado inicial
     -> [tsolucion]

backtr essolucion convertir ampliar esvalida solparcial =
  if essolucion(solparcial) then
     [convertir(solparcial)]
  else 
    foldl    --acumular 
      (\(sol_ac) -> \(nodo) -> 
        (sol_ac ++ (backtr essolucion convertir ampliar esvalida nodo)))
      [] 
      (filter esvalida (ampliar (solparcial)))


backtr_cont::
     (tsolucionParcial -> Bool)                      -- EsSolucionFinal?
     -> (tsolucionParcial -> tsolucion)              -- Convertir
     -> (tsolucionParcial -> [tsolucionParcial])     -- Ampliar
     -> (tsolucionParcial -> Bool)                   -- EsValida?
     -> tsolucionParcial                             -- Estado inicial
     -> ([tsolucion], Int)

backtr_cont essolucion convertir ampliar esvalida solparcial =
  if essolucion (solparcial) then
     ([convertir (solparcial)], 0)
  else
     foldl    --acumular 
       (\(sol_ac, nnodos_ac) -> \(nodo) -> 
          if (not (esvalida nodo)) then (sol_ac, nnodos_ac + 1)
          else 
          let (sols, masnodos) = (backtr_cont essolucion convertir 
                  ampliar esvalida nodo) in 
          (sol_ac ++ sols, nnodos_ac + masnodos + 1)
       )
       ([], 0)
       (ampliar solparcial)


backtr_prim_sol::
     (tsolucionParcial -> Bool)                      -- EsSolucionFinal?
     -> (tsolucionParcial -> tsolucion)              -- Convertir
     -> (tsolucionParcial -> [tsolucionParcial])     -- Ampliar
     -> (tsolucionParcial -> Bool)                   -- EsValida?
     -> tsolucionParcial                             -- Estado inicial
     -> [tsolucion]

backtr_prim_sol essolucion convertir ampliar esvalida solparcial =
  if essolucion (solparcial) then
     [convertir (solparcial)]
  else
     foldl    --acumular 
       (\(lprim) -> \(nodo) -> 
        case lprim of 
          [prim] -> [prim]
          [] -> backtr_prim_sol essolucion convertir ampliar esvalida nodo
       )
       []
       (filter esvalida (ampliar solparcial))

backtr_prim_sol_cont::
     (tsolucionParcial -> Bool)                      -- EsSolucionFinal?
     -> (tsolucionParcial -> tsolucion)              -- Convertir
     -> (tsolucionParcial -> [tsolucionParcial])     -- Ampliar
     -> (tsolucionParcial -> Bool)                   -- EsValida?
     -> tsolucionParcial                             -- Estado inicial
     -> ([tsolucion], Int)

backtr_prim_sol_cont essolucion convertir ampliar esvalida solparcial =
  if essolucion (solparcial) then
     ([convertir (solparcial)], 0)
  else
     foldl    --acumular 
       (\(lprim, nnodos) -> \(nodo) -> 
        case lprim of 
          [prim] -> ([prim], nnodos + 1) 
          [] -> if (not (esvalida nodo)) then ([], nnodos + 1)
                else let (solu,masnodos) = backtr_prim_sol_cont
                          essolucion convertir ampliar esvalida nodo in 
                     (solu, nnodos + masnodos + 1)
       )
       ([], 0)
       (ampliar solparcial)