Data.Tree包括unfoldTreeM_BF和unfoldForestM_BF使用monadic动作的结果构造树广度优先的功能.可以使用forest unfolder轻松编写树展开文件,因此我将重点关注后者:
unfoldForestM_BF :: Monad m =>
(b -> m (a, [b])) -> [b] -> m [Tree a]
从种子列表开始,它为每个种子应用一个函数,生成将产生树根的动作和用于下一级展开的种子.所使用的算法是稍微严格,因此,使用unfoldForestM_BF与该Identity单子是不完全一样使用纯unfoldForest.我一直试图弄清楚是否有办法让它变得懒惰而不牺牲它的O(n)时间限制.如果(正如Edward Kmett向我建议的那样)这是不可能的,我想知道是否有可能采用更具约束力的类型,特别是需要MonadFix而不是Monad.这个概念将(以某种方式)设置指向未来计算结果的指针,同时将这些计算添加到待办事项列表中,因此如果它们在早期计算的效果中是惰性的,则它们将立即可用.
我试图使用递归算法构造DFS树.
伪代码是:
DFF(G)
Mark all nodes u as unvisited
while there is an unvisited node u do
DFS(u)
.
DFS(u)
Mark u as visited
for each v in u's neighbor do
if v is not marked
DFS(v)
虽然我可以通过为un/visited节点构建某种数据结构,以简单的方式在命令式语言中轻松实现这一点,为Haskell分配动态分配或某种声明,但由于Haskell的纯粹性阻止了我,所以不可能这样做传递参数时更改数据.
data Graph a = Graph [(a,[a])] deriving (Ord, Eq, Show)
data Tree a = Node a [Tree a] deriving (Ord, Eq, Show)
type Point = (Int, Int)
type Edges = [Point]
type Path = [Point]
pathGraphFy :: Graph Point -> Point -> …我正在阅读Chris Okasaki撰写的这篇论文 ; 标题为"广度优先编号:算法设计中小练习的教训".
问题是 - 算法中的魔法是怎么发生的？有一些数字(例如图7标题为"将一个级别的输出线程化为下一级别的输入")不幸的是,也许只有我,但这个数字让我感到困惑.我不明白线程是如何发生的？
我正在尝试在haskell中编写一个代码,从A点到F点,在棋盘游戏中,本质上是一个Matrix,遵循最短的路径.
这是董事会:
AAAA
ACCB
ADEF
*
0 0 N
机器人进入字母A,在底部(它是*),并且必须到达F,在板的底部是坐标,x = 0,y = 0,并指向北.F坐标是(3,0)
诀窍是,它不能跳过多个字母,它可以从A到B,B到C等,它可以遍历类型的字母(A到A,B到B等)
它只能前进并转弯(左,右)所以让我去F的路径就是
前进,前进,右,前进,前进,前进,右,跳,右,跳,前进,左,跳,左,前进,前进
一旦达到F,就完成了.
我想尝试这种方法,使用树
A
/ \
A D
/ \
/ \
A C
/ \ / \
/ \ D C
A
/ \
/ \
A
/
/
A
/ \
B A
/ \
C F
在那之后,我只需要验证正确的路径和最短的权利？
问题是,我没有那么多使用树木的经验.
你会指出任何其他方式来获得最佳路径吗？
非常感谢你 .