双功能编程语言中的双链表 [英] Doubly Linked List in a Purely Functional Programming Language

问题描述

如何用纯粹的功能语言来做双向链接列表？也就是说，像Haskell那样，你不在Monad，所以你没有突变。可能吗？ （单链表非常简单）。

How does one go about doing doubly linked lists in a pure functional language? That is, something like Haskell where you're not in a Monad so you don't have mutation. Is it possible? (Singly linked list is obviously pretty easy).

推荐答案

在纯功能语言中，双向链表不是那么有趣。一个双向链表的想法是能够抓住一个节点，向任意一个方向移动，或者能够拼接到一个列表的中间。在纯粹的功能语言中，您可能更喜欢这两种数据结构之一：

In a pure functional language, a doubly-linked list is not that interesting. The idea of a doubly linked list is to be able to grab a node and go in either direction, or to be able to splice into the middle of a list. In a pure functionaly language you probably are better off with one of these two data structures:

• 具有指针的单链表在中间，你可以从左边或右边去（Huet的拉链的一个变体）

• A singly linked list with a pointer in the middle, from which you can go either left or right (a variant of Huet's "Zipper")

一个手指树，这是一个令人兴奋的数据结构由Ralf Hinze和Ross Paterson发明。

A finger tree, which is a mind-blowing data structure invented by Ralf Hinze and Ross Paterson.

我是拉链的大粉丝;这在很多情况下很有用。

I'm a big fan of the zipper; it's useful in a lot of situations.

这篇关于双功能编程语言中的双链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！