链表 OCaml

Question

我该如何在OCaml中创建一个链表来存储我的数据？我想创建一个单向链表，但是我却无法正确使用语法。我想要创建一个模块，简单地获取链表中的'a元素，插入'a元素或删除'a元素。

有人有任何想法吗？

- Faisal Abid

---

这是作业吗？如果是，请标记为作业。 - D.Shawley

这不是真的作业，只是在阅读有关数据结构的书籍，并想尝试在 Ocaml 中实现它。 - Faisal Abid

Answer 1

正如eccodeal所说，ocaml已经有了列表。

然而，为了您的兴趣，这是您可以构建自己的列表的方法。显然，在实际应用中，您永远不会使用它 :) 如果您想要一些树，则数据结构非常相似。

exception Empty_list

type 'a my_list = Nil | List of 'a * 'a my_list

let head = function 
     Nil -> raise Empty_list
   | List(e,_) -> e;;

let tail = function
    Nil -> Nil
   | List(_,t) -> t

let l = List(1, List(4, List(8, Nil)));;

print_endline (string_of_int(head l));;

print_endline (string_of_int (head(tail l)));;

- Tristram Gräbener

Answer 2

OCaml内置了列表：

整数列表： [1;2;3;4;5] ;; 返回：int list = [1; 2; 3; 4]

字符串列表： ["this";"that";"other"];; 返回：string list = ["this"; "that"; "other"]

或者您可以使用cons操作符::来构建列表：

1::2::3::[];; 返回：int list = [1; 2; 3]

要获取列表的头部（第一个项目）：

List.hd [1;2;3]
返回1

要获取列表的尾部（第一个项目之后的所有项目）：

List.tl [1;2;3] 返回：int list = [2; 3]

此外，您可以查看OCaml标准库中的列表实现方法，方法如下：

[OCaml的安装位置]/lib/ocaml/std-lib/list.ml

- aneccodeal

---

然而，这是否有资格作为一个具有节点等的链表？ - Faisal Abid

@Failsal：是的。虽然它实际上是一个栈（一种由链表构建的数据结构），因此您只能从列表的前面推送和弹出节点。 - Juliet

我刚在我的回答末尾添加了这句话：你可以查看以下位置中OCaml标准库中列表的实现方式:[OCaml安装位置]/lib/ocaml/std-lib/list.ml - aneccodeal

Answer 3

OCaml已经有列表作为原语了吗？我自大学以来就没有使用SML了，但我似乎记得head和tail原语。不过我看到其他人已经实现了真正的链表数据结构...例如，看看Dustin的OCaml Linkedlist。

- D.Shawley