backtracking in haskell

Question

I have to traverse a matrix and say how many "characteristic areas" of each type it has.

A characteristic area is defined as a zone where elements of value n or >n are adjacent.

For example, given the matrix:

0 1 2 2
0 1 1 2
0 3 0 0

There's a single characteristic area of type 1 which is equal to the original matrix:

0 1 2 2
0 1 1 2
0 3 0 0

There are two characteristic areas of type 2:

0 0 2 2    0 0 0 0
0 0 0 2    0 0 0 0
0 0 0 0    0 3 0 0

And one characteristic area of type 3:

0 0 0 0 
0 0 0 0
0 3 0 0 

So, for the function call:

countAreas [[0,1,2,2],[0,1,1,2],[0,3,0,0]] 

The result should be

[1,2,1]

I haven't defined countAreas yet, I'm stuck with my visit function when it has no more possible squares in which to move it gets stuck and doesn't make the proper recursive call. I'm new to functional programming and I'm still scratching my head about how to implement a backtracking algorithm here. Take a look at my code, what can I do to change it?

move_right :: (Int,Int) -> [[Int]] -> Int -> Bool
move_right (i,j) mat cond | (j + 1) < number_of_columns mat && consult (i,j+1) mat /= cond = True
               | otherwise = False

move_left :: (Int,Int) -> [[Int]] -> Int -> Bool
move_left (i,j) mat cond | (j - 1) >= 0 && consult (i,j-1) mat /= cond = True
               | otherwise = False

move_up :: (Int,Int) -> [[Int]] -> Int -> Bool
move_up (i,j) mat cond | (i - 1) >= 0 && consult (i-1,j) mat /= cond = True
               | otherwise = False

move_down :: (Int,Int) -> [[Int]] -> Int -> Bool
move_down (i,j) mat cond | (i + 1) < number_of_rows mat && consult (i+1,j) mat /= cond = True
               | otherwise = False

imp :: (Int,Int) -> Int
imp (i,j) = i


number_of_rows :: [[Int]] -> Int
number_of_rows i = length i

number_of_columns :: [[Int]] -> Int
number_of_columns (x:xs) =  length x

consult :: (Int,Int) -> [[Int]] -> Int
consult (i,j) l = (l !! i) !! j

visited :: (Int,Int) -> [(Int,Int)] -> Bool
visited x y = elem x y

add :: (Int,Int) -> [(Int,Int)] -> [(Int,Int)]
add x y = x:y

visit :: (Int,Int) -> [(Int,Int)] -> [[Int]] -> Int -> [(Int,Int)]
visit (i,j) vis mat cond | move_right (i,j) mat cond && not (visited (i,j+1) vis) = visit (i,j+1) (add (i,j+1) vis) mat cond
               | move_down (i,j) mat cond && not (visited (i+1,j) vis) = visit (i+1,j) (add (i+1,j) vis) mat cond
               | move_left (i,j) mat cond && not (visited (i,j-1) vis) = visit (i,j-1) (add (i,j-1) vis) mat cond
               | move_up (i,j) mat cond && not (visited (i-1,j) vis) = visit (i-1,j) (add (i-1,j) vis) mat cond
               | otherwise = vis

Answer 1

Would it help you to use an Array type here, rather than a list-of-lists? You are still doing functional programming, just using a better data structure.

You can create an Array (Int,Int) Int if that works for you. See:

http://hackage.haskell.org/packages/archive/array/0.2.0.0/doc/html/Data-Array-IArray.html

import Data.Array

...to get the library.

Answer 2

I don't think backtracking is actually what you are after. Seems to me that your aim is to have your visit function build up a visited list as it finds all the connected elements in the matrix from some point that meet some condition. What you need to think about is what algorithm will achieve this. Don't worry about expressing it in terms of functional or imperative programming (yet). Just think: Is the algorithm recursive in nature? Iterative? If you stopped it in the middle of computing, how would you know what to do next in the algorithm? What data would you need?

I wouldn't worry about various improvements in the code for now (using Array or eliminating the if statements, etc...), you can get to those later. The key you are missing is a viable algorithm.