8

我睡不着！:)

我在 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]
4

3 回答 3

6

双向链表可以用一种热切的语言以纯粹的功能方式实现，就像单链表上的拉链一样。例如，参见Rosetta Code > 双链表 > OCaml > Functional。

于 2012-02-14T19:33:51.057 回答
4

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

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

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

于 2012-02-14T13:18:17.493 回答
4

在 Prolog 的非回溯子集中，可以看作是显式设置一次急切的纯函数式语言，您可以轻松构建双向链表。正是引用透明性让 Haskell 变得困难，因为它禁止 Prolog 对已命名的、明确尚未设置的逻辑变量进行显式设置，而是迫使 Haskell 以“打结”的扭曲方式实现相同的效果。我认为。

另外，Haskell在惰性求值下的受保护递归与 Prolog 以尾递归模 cons方式构建的开放式列表之间并没有太大区别。国际海事组织。例如，这是 Prolog 中惰性列表的示例。memoized 共享存储用作通用访问中介，因此可以将先前计算的结果安排到缓存中。

想一想，如果您在设置任何变量或任何指针后从不重置任何变量或任何指针，那么您可以以一种限制性的方式将 C 用作一种急切的纯函数式语言。你仍然有空指针，就像 Prolog 有变量一样，它也是显式的 set-once。当然，您可以使用它构建双向链表。

所以剩下的唯一问题是，你承认这样的 set-once语言是pure吗？

于 2012-02-14T17:52:18.820 回答