haskell에서 역 추적하기

Question

행렬을 탐색하고 각 유형의 "특성 영역"이 몇 개인 지 말해야합니다.

특성 영역은 값 n 또는> n의 요소가 인접한 영역으로 정의됩니다. 제 2 형의 두 가지 특성 영역이있다

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

:

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

원래 매트릭스와 동일 유형 (1)의 하나의 특징 영역이있다 : 행렬 주어진 예

:

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

그리고 유형 3의 한 특징 영역 :

01 23,516,

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

그래서, 함수 호출 :

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

결과는 아직 countAreas을 정의하지 않은

[1,2,1] 

해야이있을 때, 나는 나의 visit 기능이 붙어있어 그것을 움직일 수있는 가능한 사각형이 더 이상 붙어 있지 않고 적절한 재귀 호출을하지 못합니다. 저는 함수형 프로그래밍에 익숙하지 않고 여기에서 역 추적 알고리즘을 구현하는 방법에 대해 여전히 머리를 쓰고 있습니다. 내 코드를 살펴보고 변경하려면 어떻게해야합니까?

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

목록 목록이 아닌 여기에 배열 유형을 사용하는 것이 도움이 되겠습니까? 더 나은 데이터 구조를 사용하여 함수형 프로그래밍을 수행하고 있습니다.

Array (Int,Int) Int을 만들 수 있습니다. 참조 :

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

import Data.Array 

가 ... 라이브러리를 얻을 수 있습니다.

Answer 2

나는 역 추적이 실제로 당신이 무엇인지 알고 싶지 않습니다. 귀하의 목표는 어떤 조건을 충족하는 어떤 지점에서 행렬의 모든 연결된 요소를 찾으면 귀하의 visit 함수가 방문 목록을 구축하도록하는 것입니다. 생각할 필요가있는 것은 무엇을 알고리즘이 달성 할 것인가입니다. 기능적 또는 필수 프로그래밍 (아직)으로 표현하는 것에 대해 걱정하지 마십시오. 생각해보십시오 : 알고리즘이 본질적으로 반복적입니까? 반복? 컴퓨팅 도중 중지 한 경우 알고리즘에서 다음에 무엇을해야하는지 어떻게 알 수 있습니까? 어떤 데이터가 필요합니까?

코드의 여러 개선 사항에 대해 (Array을 사용하거나 if 등을 사용하지 않고) 걱정하지 않으려 고합니다. 그 내용은 나중에 얻을 수 있습니다. 누락 된 핵심은 실행 가능한 알고리즘입니다.