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

4

言語にクロージャやラムダなどがある限り、いつでも怠惰をシミュレートできます。Javaでも（変数などを変更せずに）そのコードを書き直すことができます。すべての「怠惰な」操作を次のようなものでラップする必要があります。

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

もちろん、これはひどいように見えますが、それは可能です。

于 2012-02-14T13:18:17.493 に答える
4

Prolog の非バックトラッキング サブセットでは、明示的に set-once熱心な純粋な関数型言語と見なすことができ、二重リンク リストを簡単に作成できます。Haskell でそれを困難にしているのは、参照透過性です。それは、名前付きの明示的にまだ設定されていない論理変数の Prolog の明示的な設定を禁止し、代わりに Haskell に「結び目を結ぶ」というゆがんだ方法で同じ効果を達成するように強制するためです。おもう。

さらに、遅延評価の下での Haskell の保護された再帰と、末尾再帰モジュロ コンス方式で構築された Prolog の制限のないリストとの間には、実際には大きな違いはありません。IMO。たとえば、 Prologの遅延リストの例を次に示します。メモ化された共有ストレージはユニバーサル アクセス メディエーターとして使用されるため、以前の計算の結果をキャッシュするように配置できます。

考えてみると、一度設定された変数やポインターをリセットしない場合は、熱心な純粋な関数型言語として C を制限付きで使用できます。Prolog に変数があるのと同じように、まだ null ポインターがあるため、明示的に set-onceです。もちろん、それを使用して二重リンク リストを作成することもできます。

したがって、残っている唯一の質問は、そのようなセットワンス言語を純粋であると認めますか?

于 2012-02-14T17:52:18.820 に答える