纯函数式编程语言中的双向链表 [英] 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屋！