纯function编程语言中的双链表
如何用纯粹的function语言去做双向链表呢？ 那就是Haskell，你不在Monad中，所以你没有突变。 可能吗？ （单链表显然很容易）。
在一个纯粹的函数式语言中，双向链表并不是那么有趣。 双向链表的概念是能够抓取一个节点并向任一方向行进，或者能够拼接到列表的中间。 在一个纯粹的函数式语言中，用这两种数据结构中的一种可能会更好：
-
一个单独的链表，中间有一个指针，你可以从左到右（Huet的“Zipper”的一个变种）
-
一种手指树，这是Ralf Hinze和Ross Paterson发明的令人兴奋的数据结构。
我是拉链的忠实粉丝。 这在很多情况下都很有用。
有很多方法。
如果你在构build双链表之后不想改变双链表，你可以依靠懒惰来“束缚结”。
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
有趣的是，请注意，前者依赖于懒惰的成功。 你最终需要突变或懒惰来打结。
我会重申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 在OCaml中，对于循环链表，你总是可以这样做：
type t = { a : t Lazy.t } let cycle n = let rec start = {a = lazy (aux n) } and aux = function | 0 -> start | n -> { a = lazy (aux (n-1))} in start
对于双向链表，我想有可能做类似的事情。 但是在打字的时候，你必须要依赖懒惰和logging的友好结构。 快速和肮脏的循环双向链表：
type 'at = { data : 'a; before : 'at Lazy.t; after : 'at Lazy.t } let of_list l = match l with [] -> assert false | hd::tl -> let rec start = { data = hd; before = last; after = next } and couple = lazy (aux (lazy start) hd) and next = lazy (Lazy.force (fst (Lazy.force couple))) and last = lazy (Lazy.force (snd (Lazy.force couple))) and aux before = function | [] -> (lazy start), before | hd::tl -> let rec current = lazy { data = hd; before = before; after = after } and couple = lazy (aux current tl) and after = lazy (Lazy.force (fst (Lazy.force couple))) and last = lazy (Lazy.force (snd (Lazy.force couple))) in current, last in start
