algorithm - 优化在Haskell中实现的BFS

所以我想写一个图表宽度优先搜索。该算法跟踪其状态下的一些值。这些是：每个节点和队列的avisited状态。
它还需要知道图的边和它的目标目标是什么，但这不会在步骤中改变。
这就是我想出来的（对不起丑女人）

import Prelude hiding (take, cons, drop)
import Data.Vector

type BFSState = (Vector Bool, Vector [Int], [Int], Int)
bfsStep :: BFSState -> BFSState
bfsStep (nodes, edges, current:queue, target)
    | current == target = (nodes, edges, [], target)
    | nodes ! current = (nodes, edges, queue, target)
    | otherwise = (markedVisited, edges, queue Prelude.++ (edges ! current), target)
    where
        markedVisited = (take current nodes) Data.Vector.++ (cons True (drop (current + 1) nodes))

bfsSteps :: BFSState -> [BFSState]
bfsSteps init = steps
    where steps = init : Prelude.map bfsStep steps

bfsStep接受一个状态并生成下一个状态当状态的队列为[]时，已找到目标节点。bfsSteps只是使用一个自引用列表来生成一个BFSStates的列表。现在，还没有办法确定到达某个节点需要多少步骤（给定启动条件），但是bfsSteps函数将生成算法所采取的步骤。
我担心的是，这个州的每一步都会被复制我意识到与++的连接并不能很好地执行，但是我觉得这并不重要，因为每个步骤都会复制所有的状态。
我知道有些单子应该做我在这里所做的，但是既然haskell是纯的，这不意味着单子还必须复制状态吗？
难道没有办法说“嘿，我在代码中只使用了一次这些值，而且我没有在任何地方存储它们你可以改变它们而不是制造新的“？
如果haskell自己这么做，它仍然允许我保持代码的纯净，但使执行速度更快。

最佳答案

你的状态只有在修改时才会被复制，而不是在使用时。
例如，edges :: Vector [Int]从不被bfsStep修改，因此相同的值在所有递归调用中都被重用。
另一方面，bfsStep以两种方式修改您的queue :: [Int]：
将其拆分为current : queue-但这会重用原始队列的尾部，因此不会进行复制
用Prelude.++附加到它。这需要O(queue size)复制。
在更新nodes :: Vector Int以包含新节点时，也需要进行类似的复制。
有几种方法可以减少对queue的复制，也有几种方法可以减少对nodes的复制。
对于nodes可以将计算包装在ST smonad中，以使用单个可修改向量。或者，您可以使用功能性数据结构，如IntMap，它具有fairly fast update。
对于您的queue可以使用data.sequence或a two list implementation。

关于algorithm - 优化在Haskell中实现的BFS，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22720364/