惰性评估与急切评估以及双链表构建

我睡不着！ :)

我用 Haskell 编写了构建双链表的小程序。基本语言的属性是惰性求值（请参阅下面的一堆代码）。我的问题是我可以在pure函数式语言与eager评价还是不评价？无论如何，有什么属性eager函数式语言必须能够构建这样的结构（杂质？）？

import Data.List

data DLList a = DLNull |
    DLNode { prev :: DLList a
           , x :: a
           , next :: DLList a
           }
  deriving (Show)

walkDLList :: (DLList a -> DLList a) -> DLList a -> [a]
walkDLList _ DLNull = []
walkDLList f n@(DLNode _ x _)  = x : walkDLList f (f n)

-- Returns first and last items.
makeDLList :: [a] -> (DLList a, DLList a)
makeDLList xs = let (first, last) = step DLNull xs in (first, last)
  where
    step prev [] = (DLNull, prev)
                         -- Here I use laziness. 'next' is not built yet, it's a thunk.
    step prev (x : xs) = let this = DLNode prev x next 
                             (next, last) = step this xs
                         in (this, last)

testList :: [Int] -> IO ()
testList l = let
    (first, last) = makeDLList l
    byNext = walkDLList next first
    byPrev = walkDLList prev last
  in do
    putStrLn $ "Testing: " ++ show l
    print byNext
    print byPrev

main = do
  testList []
  testList [1, 2, 3, 4]

双向链表可以用 Eager 语言以纯函数方式实现，如zipper http://learnyouahaskell.com/zippers在单链表上。例如，参见Rosetta 代码 > 双向链表 > OCaml > 函数式 http://rosettacode.org/wiki/Doubly-linked_list/Element_definition#Functional.