Neighbourhood.hs

-----------------------------------------------------------------------------
-- |
-- Module      :  Control.Search.Local.Neighbourhood
-- Copyright   :  (c) Richard Senington & David Duke 2010
-- License     :  GPL-style
-- 
-- Maintainer  :  Richard Senington <sc06r2s@leeds.ac.uk>
-- Stability   :  provisional
-- Portability :  portable
-- 
-- Simple Neighbourhood functions for the representation of problems to the library.
-- All neighbourhood functions must ultimately be of the form a->[a].
--
-- This module also contains some additional code for the modeling of problems and the 
-- link between the model and the library.
----------------------------------------------------------------------------- 

module Control.Search.Local.Neighbourhood (
  exchange,
  basicExchange,
  NumericallyPriced(priceSolution)
) where

import Data.List

-- | following helper function pinched from http://www.polyomino.f2s.com/david/haskell/combinatorics.html 

combinationsOf 0 _ = [[]]
combinationsOf _ [] = []
combinationsOf k (x:xs) = map (x:) (combinationsOf (k-1) xs) ++ combinationsOf k xs

{- | my code again from here on

The first type of neighbourhood is based upon combination exchange in a sequence of elements. This is appropriate for something like TSP, where
order matters, but would be less useful for SAT.

It takes 2 numbers as parameters, one of which is the number of exchanges to perform, the other the maximum distance within the list. 
For example exchange 2 2, would change up to 2 elements in each neighbourhood, either adjacent or separated by 1 other element. -}

exchange :: Eq a=>Int->Int->[a]->[[a]]
exchange _ 0 inlist = [inlist]
exchange exchanges dist inlist = nub (map (implement inlist) variants)
  where
    len = (length inlist -1)
    opts = [(x,x+y) | x<-[0..len],y<-[1..dist],x+y<= len]
    variants = combinationsOf exchanges opts
    implement :: [a]->[(Int,Int)]->[a] 
    implement i [] = i 
    implement i ((x,y):xs) = implement (begin++[x2]++middle++[x1]++rest') xs
      where
        (begin,x1:rest) = splitAt x i
        (middle,x2:rest') = splitAt (y-x-1) rest

-- | We provide the most basic exchange system for testing

basicExchange :: Eq a=>[a]->[[a]]
basicExchange = exchange 1 1

{- | 
Some transformations (and the manual inspector of the search process) need to be able to extract a numeric price from 
a solution. To use these, the solution representation data type must be a part of the following class, please see 
the example code. -}

class (Ord b,Num b)=>NumericallyPriced a b | a->b where
  priceSolution :: a->b