Rollback in haskell
I need to traverse the matrix and say how many "characteristic areas" of each type it has.
A characteristic region is defined as a region where elements of value n or> n are adjacent.
For example, given a matrix:
0 1 2 2
0 1 1 2
0 3 0 0
There is one characteristic region 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, to call the function:
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 tied to my function visit
when it has no more possible squares to move it to, gets stuck and doesn't make the correct recursive call. I am new to functional programming and I am still scratching my head on how to implement the backtracking algorithm. 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
source to share
Would it help you to use an array type here rather than a list of lists? You are still doing functional programming just by using a better data structure.
You can create Array (Int,Int) Int
if it works for you. Cm:
http://hackage.haskell.org/packages/archive/array/0.2.0.0/doc/html/Data-Array-IArray.html
import Data.Array
... to get the library.
source to share
I don't think rollback is what you want. It seems to me that your goal is for your function to visit
create a visited list since it detects all related elements in the matrix from some point that satisfy some condition. What you need to think about is that the algorithm will achieve this. Don't worry about expressing this in functional or imperative programming terms (yet). Think: is it a recursive algorithm in nature? Recurring? If you stop it in the middle of a computation, how do you know what to do next in the algorithm? What data do you need?
I wouldn't worry about the various code improvements at the moment (using Array
or excluding operators if
, etc.), you can refer to them later. The key you are missing is a viable algorithm.
source to share