OCaml在列表中插入元素

将元素插入到OCaml中的列表中的特定位置的标准方式是什么？只允许递归。不允许分配操作。OCaml在列表中插入元素

我的目标是通过使用in_degree = out_degree = 1删除顶点来压缩ocaml中的图。出于这个原因，我需要删除相邻的边缘以形成单个边缘。现在边缘列表[（6,7）;（1,2）;（2,3）;（5,4）]。所以我需要从列表中删除这些边并添加一个边。所以上面的列表现在看起来像[（6,7）;（1,3）;（5,4）]。这里我们看到（1,2）;（2,3）被删除，（1,3）被插入到第二个位置。我为此设计了一个算法。但为此，我需要知道如何从位置2,3删除边（1,2）;（2,3），并且在位置2中插入（1,3）而没有任何显式变量并以递归方式。

来源

2012-02-29 P basak

我会建议，如果可能的话，抛出清单并使用Set数据结构。 – nlucaroni 2012-02-29 17:02:12

“只允许递归”，“没有任何显式变量” - 听起来像某种功课......是吗？ – lambdapower 2012-03-01 17:51:04

是的，这是作业的一部分，但我没有要求解决作业问题。我设计了一个算法，并使用我需要在列表中执行此操作的算法。那是我问的。我的作业是在ocaml中压缩图表。在这里，我不是在问这个问题。我在问清单。 – 2012-03-02 10:32:11

OCaml的名单是不可改变的所以有喜欢删除和插入在列表的操作元素没有这样的事情。

你可以做的是通过重新使用旧列表的某个部分来创建一个新列表。例如，要从(1, 2)::(2, 3)::xs'创建一个列表(1, 3)::xs'，您实际上重新使用xs'并使用cons构造函数创建新列表。

和模式匹配是非常方便的使用方法：

let rec transform xs =            
    match xs with 
    | [] | [_] -> xs 
    | (x, y1)::(y2, z)::xs' when y1 = y2 -> (x, z)::transform xs' 
    | (x, y1)::(y2, z)::xs' -> (x, y1)::transform ((y2, z)::xs')

来源

2012-02-29 12:23:24 pad

嗨，这项工作，如果边缘不相邻的列表中，例如，如果列表是像[（1,2）;（6,7）;（5,4）;（2,3）]？ – 2012-02-29 12:32:30

它不会。该代码仅仅是为了演示使用模式匹配和'cons'构造函数进行列表操作的想法。 – pad 2012-02-29 12:35:33

你可以做这样的事情：

let rec compress l = match l with            
    [] -> []               
| x :: [] -> [x]              
| x1 :: x2 :: xs -> 
    if snd x1 = fst x2 then 
    (fst x1, snd x2) :: compress xs 
    else x1 :: compress (x2 :: xs)

来源

2012-02-29 12:16:33 cago

高度如果边缘在列表中不相邻？它会起作用吗？ – 2012-02-29 12:33:58

不，它不会。 – cago 2012-02-29 12:47:09

您使用了错误的数据结构来存储您的边缘，你的问题犯规表明您不能选择不同的数据结构。正如其他海报已经说过的：列表是不可变的，因此重复删除它们内部的元素是相对昂贵的（O（n））操作。

我也不明白为什么你必须重新插入位置2处的新边缘。图形由G =（V，E）定义，其中V和E是顶点和边缘的集合。它们的顺序并不重要。这种图形的定义也已经告诉你一个更好的边缘数据结构：集合。

OCaml中，集由平衡二叉树，以便插入和成员的缺失的平均复杂度是O（log n）的表示。所以你看到，为了删除成员，这个复杂度肯定比列表（O（n））要好，但是将成员添加到一个集合中比使用cons将元素添加到列表要更昂贵操作。

另一种数据结构是一个散列表，其中可以在O（1）时间内完成插入和删除操作。让哈希表中的键是你的边缘，因为你不使用这些值，只需使用一个常数，如单位或0.

来源

2013-04-09 08:45:39 josch

OCaml在列表中插入元素

回答

相关问题