title: backtracking in haskell
body: <p>I have to traverse a matrix and say how many "characteristic areas" of each type it has. </p>
  
  <p>A characteristic area is defined as a zone where elements of value n or >n are adjacent. </p>
  
  <p>For example, given the matrix: </p>
  
  <pre><code>0 1 2 2
  0 1 1 2
  0 3 0 0
  </code></pre>
  
  <p>There's a single characteristic area of type 1 which is equal to the original matrix:</p>
  
  <pre><code>0 1 2 2
  0 1 1 2
  0 3 0 0
  </code></pre>
  
  <p>There are two characteristic areas of type 2:</p>
  
  <pre><code>0 0 2 2    0 0 0 0
  0 0 0 2    0 0 0 0
  0 0 0 0    0 3 0 0
  </code></pre>
  
  <p>And one characteristic area of type 3:</p>
  
  <pre><code>0 0 0 0 
  0 0 0 0
  0 3 0 0 
  </code></pre>
  
  <p>So, for the function call:</p>
  
  <pre><code>countAreas [[0,1,2,2],[0,1,1,2],[0,3,0,0]] 
  </code></pre>
  
  <p>The result should be</p>
  
  <pre><code>[1,2,1]
  </code></pre>
  
  <p>I haven't defined countAreas yet, I'm stuck with my <code>visit</code> 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?</p>
  
  <pre><code>move_right :: (Int,Int) -&gt; [[Int]] -&gt; Int -&gt; Bool
  move_right (i,j) mat cond | (j + 1) &lt; number_of_columns mat &amp;&amp; consult (i,j+1) mat /= cond = True
                 | otherwise = False
  
  move_left :: (Int,Int) -&gt; [[Int]] -&gt; Int -&gt; Bool
  move_left (i,j) mat cond | (j - 1) &gt;= 0 &amp;&amp; consult (i,j-1) mat /= cond = True
                 | otherwise = False
  
  move_up :: (Int,Int) -&gt; [[Int]] -&gt; Int -&gt; Bool
  move_up (i,j) mat cond | (i - 1) &gt;= 0 &amp;&amp; consult (i-1,j) mat /= cond = True
                 | otherwise = False
  
  move_down :: (Int,Int) -&gt; [[Int]] -&gt; Int -&gt; Bool
  move_down (i,j) mat cond | (i + 1) &lt; number_of_rows mat &amp;&amp; consult (i+1,j) mat /= cond = True
                 | otherwise = False
  
  imp :: (Int,Int) -&gt; Int
  imp (i,j) = i
  
  
  number_of_rows :: [[Int]] -&gt; Int
  number_of_rows i = length i
  
  number_of_columns :: [[Int]] -&gt; Int
  number_of_columns (x:xs) =  length x
  
  consult :: (Int,Int) -&gt; [[Int]] -&gt; Int
  consult (i,j) l = (l !! i) !! j
  
  visited :: (Int,Int) -&gt; [(Int,Int)] -&gt; Bool
  visited x y = elem x y
  
  add :: (Int,Int) -&gt; [(Int,Int)] -&gt; [(Int,Int)]
  add x y = x:y
  
  visit :: (Int,Int) -&gt; [(Int,Int)] -&gt; [[Int]] -&gt; Int -&gt; [(Int,Int)]
  visit (i,j) vis mat cond | move_right (i,j) mat cond &amp;&amp; not (visited (i,j+1) vis) = visit (i,j+1) (add (i,j+1) vis) mat cond
                 | move_down (i,j) mat cond &amp;&amp; not (visited (i+1,j) vis) = visit (i+1,j) (add (i+1,j) vis) mat cond
                 | move_left (i,j) mat cond &amp;&amp; not (visited (i,j-1) vis) = visit (i,j-1) (add (i,j-1) vis) mat cond
                 | move_up (i,j) mat cond &amp;&amp; not (visited (i-1,j) vis) = visit (i-1,j) (add (i-1,j) vis) mat cond
                 | otherwise = vis
  </code></pre>