懒惰与急切的评估和双链表建设

Question

我睡不着!:)

我在Haskell编写了一个构建双链表的小程序.基本语言的属性是懒惰的评估(参见下面的一堆代码).我的问题是,我可以做在同一个纯粹的功能性语言急于评估或不？在任何情况下,渴望功能语言必须具备哪些属性才能构建这样的结构(杂质？)？

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]

Answer 1

双向链表可以用纯粹的功能方式以急切的语言实现,作为单链表上的拉链.例如,参见Rosetta Code> Doubly-linked list> OCaml> Functional.

Answer 2

只要一种语言有闭包、lambda 等东西，你总是可以模拟惰性。你甚至可以用 Java 重写该代码（无需改变变量等），你只需要将每个“惰性”操作包装在类似的内容中

interface Thunk<A> {
   A eval();  
}

当然，这看起来很糟糕，但这是可能的。