Lazy vs нетерпеливая оценка и построение двойного списка

Question

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

Я написал небольшую программу, создав двойной связанный список в Haskell. Свойство основного языка, чтобы сделать это, было ленивой оценкой (см. Кучу кода ниже). И мой вопрос: могу ли я сделать то же самое в чистом функциональном языке с 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] 

Answer 1

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

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

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

Answer 2

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

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

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

Так что единственный вопрос, который остается, как вы признать такие набор однократно языков в качестве чистого?

Answer 3

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