学习一些Scala和计划生育的好处后，我重新实现了一些我以前的CS分配，以更好地理解FP。 不过，我得似乎不切实际与FP（或至少是平凡的翻译）来实现一个任务。
当解决一个简单的2D迷宫，有必要记住已访问哪些节点。 然而，如果没有共享的状态，如何在每个递归调用知道什么节点上的其他递归调用已经检查？ 我能通过迷宫作为参数传递给每一个递归调用和返回包含去过的地方一个新的迷宫，但似乎过于计算密集型复制整个迷宫每次递归调用。 将一个更先进的方法需要实现一个不可变的迷宫求解？
Answer 1:
您可以绕过包含访问节点的集合（或它们的ID /名称，如果节点本身是在你的安装可比平等）。 将项目添加到一个不可变组一般需要O(log n) ，所以没有检查的元件是否被包含在该组。 所以，这不是复制迷宫显著便宜。
Answer 2:
也许你注意到了我刚才的答案被删除。 虽然我取笑，仅表明“红色所有的死角和绿色通道电脑显示的入口连接到出口，”在同一时间，它是我所理解的比喻功能模式 - 一种包含预先计算确定性。 鉴于我有限的理解和认识，我的工作在Haskell避免递归深度搜索，计算路径为一个4x5迷宫一个例子，给定的一个阵列，其中在迷宫的每个小区（即，每个数组元素）只包含的索引细胞它可以连接到; 和-1入口，-2退出。 （你可以看到在代码段的顶部迷宫的轮廓。）我知道，更多的有经验的程序员可以做更多，更好。 请让我知道这看起来很适合在这个问题的精神（谢谢你，安德鲁，对于有趣的挑战/方向）。
{-M A Z E-}
[E]=[ ]=[ ]=[ ]
|
[ ]=[ ]=[ ]=[ ]
| |
[ ] [ ]=[ ] [ ]
| | |
[ ] [ ]=[ ]=[ ]
| |
[ ]=[ ]=[ ]=[E]
import Data.List
import Data.Maybe
--Each element in the maze lists the indexes of connected cells, '-1' for entrance, '-2' for exit
maze = [[-1,1], [0,2,5], [1,3], [2],
[5], [4,6,1,9], [5,7], [6,11],
[12], [5,13,10], [9], [7,15],
[8,16], [14,9,17], [13,15], [14,11],
[12,17], [13,16,18], [17,19], [18,-2]]
maze' = [[-1,1], [0,2], [1,3], [2,7],
[8,5], [4,6], [5,7], [3,6],
[4,9], [8,10], [9,11], [10,15],
[16,13], [12,14], [13,15], [11,14],
[12,17], [16,18], [17,19], [18,-2]]
index a = fromJust $ elemIndex a maze
indexes a = map (index) a
areConnected index_a index_b = elem index_a (maze !! index_b)
isStart a --(a :: cell)
| elem (-1) a = True
| otherwise = False
isEnd a --(a :: cell)
| elem (-2) a = True
| otherwise = False
hasStart a --(a :: [cell])
| isStart (head a) = True
| otherwise = False
hasEnd a --(a :: [cell])
| isEnd (last a) = True
| otherwise = False
isSequenced (w:x:xs) (y:z:zs) --includes possibility of overlap since we do not know how many cells comprise the solution
| areConnected (index $ last xs) (index y)
|| last xs == y
|| let (b:c:cs) = reverse (w:x:xs) in [c,b] == [y,z] = True
| otherwise = False
removeBacktracks (x:xs)
| (x:xs) == [] = []
| xs == [] = [x]
| x == head xs = removeBacktracks xs
| length xs > 1 && x == let (y:ys) = xs in head ys = removeBacktracks (tail xs)
| otherwise = x : removeBacktracks xs
--list dead ends
dead_ends = filter (\x -> length x==1 && find (==(-1)) x == Nothing) maze
dead_ends_indexes = map (index) dead_ends
connectedToDeadEnd (x:xs)
| x `elem` dead_ends_indexes = True
| not (x `elem` dead_ends_indexes) && xs == [] = False
| otherwise = connectedToDeadEnd xs
--list first from dead ends
first_from_dead_ends = filter (\x -> length x==2 && find (==(-1)) x == Nothing && connectedToDeadEnd x) maze
--create sequences
filtered = [l | l <- maze, not (elem l dead_ends) && not (elem l first_from_dead_ends)]
sequences_3 = [[a,b,c] | a <- filtered, not (isEnd a),
b <- filtered, not (isEnd b || isStart b), areConnected (index a) (index b),
c <- filtered, not (isStart c), a /= c, areConnected (index b) (index c)]
sequences_4 = [a ++ [b] | a <- sequences_3, not (hasEnd a), b <- filtered,
last a /= b, areConnected (index $last a) (index b)]
paths = take 1 [indexes $ concat [a, b, c, d, e] | a <- sequences, hasStart a,
b <- sequences, not (hasStart b || hasEnd b),
isSequenced a b,
c <- sequences, b /= c, not (hasStart c || hasEnd c),
isSequenced b c,
d <- sequences, c /= d, not (hasStart d || hasEnd d),
isSequenced c d,
e <- sequences, hasEnd e,
isSequenced d e]
where sequences
| length filtered < 16 = sequences_3
| otherwise = sequences_4
path = removeBacktracks $ head paths
main = print path
--outputs: [0,1,5,9,13,17,18,19]
文章来源: Simplest way to solve a maze without mutability
