Ленивая и энергичная оценка и создание двойного связанного списка - PullRequest
Новая
       30

Ленивая и энергичная оценка и создание двойного связанного списка

8 голосов
/ 14 февраля 2012

Я не могу спать!:)

Я написал небольшую программу, строящую двойной связанный список в 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]

Ответы [ 3 ]

6 голосов
/ 14 февраля 2012

Двусвязный список может быть реализован чисто функциональным способом на нетерпеливом языке как застежка-молния в односвязном списке. См., Например, Rosetta Code> Двусвязный список> OCaml> Функциональный .

4 голосов
/ 14 февраля 2012

В подмножестве Prolog без обратной проверки, которое можно рассматривать как явно установленный один раз нетерпеливый чистый функциональный язык, вы можете легко создавать списки с двойной связью.Именно ссылочная прозрачность делает это затруднительным в Haskell, поскольку он запрещает явной установке Пролога с именем , явно еще не заданных логических переменных, и вместо этого заставляет Haskell достигать того же самогоэффект искривленным способом «завязывания узла».Я думаю.

Кроме того, на самом деле нет большой разницы между защищенной рекурсией Haskell при ленивой оценке и открытыми списками Пролога, построенными в хвостовой рекурсии по модулю cons .ИМО.Вот, например, пример ленивых списков в Прологе .Записанное общее хранилище используется в качестве универсального посредника доступа, поэтому результаты предыдущих вычислений можно упорядочить для кэширования.

Если подумать, вы можете использовать C ограничительным образом в качестве чисто функционального языка, если вы никогда не сбрасываете ни переменную, ни указатель, как только он установлен.У вас все еще есть нулевые указатели, точно так же, как в Прологе есть переменные, так что это тоже явно установленный один раз .И, конечно, вы можете создавать двусвязные списки с ним.

Таким образом, остается только один вопрос: допускаете ли вы такие однократные языки как pure ?

4 голосов
/ 14 февраля 2012

Пока в языке есть что-то вроде замыканий, лямбд и т. Д., Вы всегда можете имитировать лень.Вы можете переписать этот код даже в Java (без изменения переменных и т. Д.), Вам просто нужно обернуть каждую «ленивую» операцию чем-то вроде 

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

Конечно, это будет выглядеть ужасно, но это возможно.

...