懒惰vs渴望评估和双链表建设 [英] Lazy vs eager evaluation and double linked list building

问题描述

我睡不着！ ：）

我在Haskell编写了一个小程序构建双链表。基本语言的属性使其成为懒惰评估（请参阅下面的一堆代码）。我的问题是我可以用 eager 评估或不用纯功能语言来做同样的事情吗？无论如何， 功能语言必须能够构建这样的结构（杂质？）？

 导入Data.List 
 
数据DLList a = DLNull | 
 DLNode {prev :: DLList a 
，x :: a 
，next :: DLList a 
} 
派生（显示）
 
 walkDLList ::（DLList a  - > DLList a） - > DLList a  - > [a] 
 walkDLList _ DLNull = [] 
 walkDLList f n @（DLNode _ x _）= x：walkDLList f（f n）
 
  - 返回第一个和最后一个项目。 
 makeDLList :: [a]  - > （DLList a，DLList a）
 makeDLList xs = let（first，last）= step DLNull xs in（first，last）
其中
 step prev [] =（DLNull，prev）
  - 在这里我使用懒惰。 '下一个'还没有建成，这是一个thunk。 
 step prev（x：xs）= let this = DLNode prev x next 
（next，last）=步骤这个xs 
 in（this，last）
 
 testList :: [Int]  - > IO（）
 testList l = let 
（first，last）= makeDLList l 
 byNext = walkDLList next 
 byPrev = walkDLList prev last 
 in 
 putStrLn $Testing：++ show l 
 print byNext 
 print by prev 
 
 main = do 
 testList [] 
 testList [1，2 ，3，4] 
  

解决方案

双向链表以单一链接列表中的拉链的形式，以热切语言的纯粹功能性方式实现。例如，参见 Rosetta Code>双链表> OCaml> Functional 。

I can't sleep! :)

I've written small program building double linked list in Haskell. The basic language's property to make it was lazy evaluation (see the bunch of code below). And my question is can I do the same in a pure functional language with eager evaluation or not? In any case, what properties eager functional language must have to be able to build such structure (impurity?)?

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]

解决方案

A doubly-linked list can be implemented in a purely functional way in an eager language as a zipper on a singly-linked list. See, for example, Rosetta Code > Doubly-linked list > OCaml > Functional.

这篇关于懒惰vs渴望评估和双链表建设的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！