时间戳

首页 > 解决方案 > 如何使用地图构建列表？

list - 如何使用地图构建列表？

问题描述

首先，我有这些类型：

type position = float * float

type node = position

为了构建我的地图，我编写了这些模块：

module MyMap =
  struct
    type t = Graph.node
    let compare (a1,b1) (a2,b2) =
      if a1 > a2 then 1
       else if a1 < a2 then -1
       else if b1 > b2 then 1
       else if b1 < b2 then -1
       else 0
  end

module DistMap = Map.Make(MyMap)

就我而言，我将有一个previousMap类型val previousMap : (float * float) DistMap.t = <abstr> 它包含节点作为键和值。假设它是这样构建的：

DistMap.bindings prevMap;;
- : (node * (float * float)) list =
[((1., 1.), (2., 2.)); 
((2., 2.), (3., 3.)); 
((3., 3.), (4., 4.));
((4., 4.), (5., 5.))]

这意味着 (2.,2.) 是图中 (1.,1.) 的前驱节点。

我的目标是构建表示从source节点到target节点的路径的列表。

例如，如果我有：

let build_path prevMap source target

使用 的预期输出previousMap将是node (or float * float) list这样的：

build_path previousMap (1.,1.) (5.,5.) -> [(1.,1.);(2.,2.);(3.,3.);(4.,4.);(5.,5.)]

到目前为止，我的尝试包括尝试在 the 上使用foldanditer功能，previousMap但没有结果。

更新 ：

这是我认为可能接近我想要实现的尝试：

let build_list map source target =
  let rec build_aux acc map source x =
    if ((DistMap.find x map)) = source then source::acc
    else build_aux (DistMap.find x map)::acc source (DistMap.find x map)
    in build_aux [] map source target

但是我得到这个错误输出：

356 |     else build_aux (DistMap.find x map)::acc source (DistMap.find x map)
                         ^^^^^^^^^^^^^^^^^^^^
Error: This expression has type 'a but an expression was expected of type
         'a list
       The type variable 'a occurs inside 'a list

更新 2：

问题已解决，但功能未按预期运行。基本上这是我想实现的伪代码：

伪代码

我怎样才能着手建立这样的清单？

谢谢。

标签： listdictionaryocaml

解决方案

fold和的问题iter在于它们以它们自己确定的顺序处理节点。本质上，顺序基于地图的形状，由键确定。您希望按照地图中的值确定的顺序处理地图的节点。

我很确定唯一的方法是编写自己的专用递归函数。

更新

在最新的代码中，你有这个表达式：

build_aux (DistMap.find x map)::acc source (DistMap.find x map)

OCaml 中将函数参数绑定到函数的运算符优先级非常严格，因此解析如下：

(build_aux (DistMap.find x map)) :: (acc source (DistMap.find x map))

您需要在此子表达式周围加上括号：

((DistMap.find x map)::acc)

推荐阅读