纯函数式编程语言中的双重链接列表

Question

如何用纯函数式语言编写双向链表？也就是说,像Haskell这样的东西,你不在Monad,所以你没有变异.可能吗？(单链表很明显很简单).

Answer 1

在纯函数式语言中,双向链表并不那么有趣.双向链表的想法是能够抓住节点并朝任一方向前进,或者能够拼接到列表的中间.在纯函数式语言中,您最好使用以下两种数据结构之一:

• 一个单独链接的列表,中间有一个指针,您可以从左侧或右侧(Huet的"Zipper"的变体)

• 手指树,是由Ralf Hinze和Ross Paterson发明的令人兴奋的数据结构.

我是拉链的忠实粉丝; 它在很多情况下都很有用.

Answer 2

有很多方法.

如果你不想在构建它之后改变双向链表,你就可以依靠懒惰来"打结".

http://www.haskell.org/haskellwiki/Tying_the_Knot

如果你想要一个可变的双向链表,你需要以某种方式伪造引用 - 或者使用真正的引用 - 这是Oleg Kiseylov提出并在这里实现的技巧:

http://hackage.haskell.org/packages/archive/liboleg/2009.9.1/doc/html/Data-FDList.html

有趣的是,请注意前者从根本上依赖懒惰来取得成功.你最终需要突变或懒惰来打结.

Answer 3

我会重申musicfan的问题:"你到底需要什么呢？" 正如Norman Ramsey所说:如果你需要多向遍历,那么拉链就更容易了; 如果你需要快速拼接,手指树很好用.

但是,只是看它看起来如何......

import Control.Arrow
import Data.List

data LNode a = LNode { here :: a, prev :: LList a, next :: LList a }
type LList a = Maybe (LNode a)

toList :: LList a -> [a]
toList = unfoldr $ fmap $ here &&& next

fromList :: [a] -> LList a
fromList l = head nodes where
    nodes = scanr ((.) Just . uncurry LNode) Nothing $ zip l $ Nothing : nodes

append :: LList a -> LList a -> LList a
append = join Nothing where
    join k (Just a) b = a' where
        a' = Just $ a { prev = k, next = join a' (next a) b }
    join k _ (Just b) = b' where
        b' = Just $ b { prev = k, next = join b' Nothing (next b) }
    join _ _ _ = Nothing