3

次のプログラムでは、一定のメモリで実行することのみを期待cycle3します (結び目を明示的に結びます)。ただし、cycle2理解できない理由により、一定のメモリでも実行されます。なぜなら、私cycle2はまったく同じ仕事をすることを期待していますcycle1

xs' = xs ++ xs'
xs' = xs ++ xs ++ xs' -- substitute value of xs'
xs' = xs ++ xs ++ xs ++ xs' -- substitute value of xs' again
xs' = xs ++ xs ++ xs ++ ... -- and so on

誰かが私がここで見逃していることを説明できますか?

module Main where

import System.Environment (getArgs)

cycle1 :: [a] -> [a]
cycle1 [] = error "empty list"
cycle1 xs = xs ++ cycle1 xs

cycle2 :: [a] -> [a]
cycle2 [] = error "empty list"
cycle2 xs = xs' where xs' = xs ++ xs'

cycle3 :: [a] -> [a]
cycle3 [] = error "empty list"
cycle3 xs = let
  xs' = go xs' xs
  in xs'
  where
    go :: [a] -> [a] -> [a]
    go start [last] = last : start
    go start (x:xs) = x : go start xs

testMem :: (Show a) => ([a] -> [a]) -> [a] -> IO ()
testMem f xs = print (xs', xs') -- prints only first val, need second val holds onto reference
  where
    xs' = f xs

main :: IO ()
main = do
  args <- getArgs
  let mCycleFunc = case args of
        ["1"] -> Just cycle1
        ["2"] -> Just cycle2
        ["3"] -> Just cycle3
        _ -> Nothing
  case mCycleFunc of
    Just cycleFunc -> testMem cycleFunc [0..8]
    Nothing -> putStrLn "Valid args are one of {1, 2, 3}."
4

2 に答える 2

6

cycle1サイクルが消費されるたびに新しいリストを作成します。その理由は明らかなはずです。

cycle2ただし、これは行いません。xs'独自の定義内で使用されるvariable を作成します。を消費するたびに関数cycle1を再評価する必要がありましたが、再帰関数はありません。すでに既知の値を持つ同じ変数を参照するだけです。cycle1xscycle2

于 2012-07-09T21:58:13.583 に答える
3

それは、等しいサンクの共有または非共有に帰着します。2つの等しいサンクは、同じ結果を生成することが保証されているサンクです。の場合、の終わりにヒットするたびcycle1に新しいサンクを作成します。そのサンクに新しいメモリを割り当てる必要があり、その値を最初から計算する必要があります。これにより、新しいリストのペアが割り当てられます。cycle1 xs[]xs

名前を変更するcycle2と、これを回避する方法が理解しやすくなると思います（「エラーオン」の場合を削除しました）。xs'result[]

cycle2 :: [a] -> [a]
cycle2 xs = result 
    where result = xs ++ result

この定義は意味的には同等ですcycle1（同じ引数に対して同じ結果を生成します）が、メモリ使用量を理解するための鍵は、サンクが作成されるという観点からそれを調べることです。この関数のコンパイル済みコードを実行すると、すぐに実行されるのは、のサンクを作成することだけですresult。サンクは、多かれ少なかれ次のように変更可能なタイプと考えることができます（完全に構成された擬似コード）。

type Thunk a = union { NotDone (ThunkData a), Done a }
type ThunkData a = struct { force :: t0 -> ... -> tn -> a
                          , subthunk0 :: t0
                          , ...
                          , subthunkn :: tn }

これは、必要な値のサンクへのポインターと、これらのサンクを強制するコードへのポインターを含むレコード、または計算の結果のいずれかです。の場合cycle2、サンクはresultのオブジェクトコードを指し、サンクはとのオブジェクトコードを(++)指しxsますresult。この最後のビットは、サンクがresultそれ自体へのポインタを持っていることを意味します。これは、一定のスペースの動作を説明しています。強制の最後のステップは、resultそれ自体を指すようにすることです。

一方、の場合cycle1、サンクには、のコード(++)、のサンクxs、およびゼロから計算するための新しいサンクがあります。cycle1 xs原則として、コンパイラーは、この後者のサンクへの参照を「親」チャンクへの参照に置き換えることができることを認識することができますが、コンパイラーはそれを行いません。一方、cycle2それは仕方がありません（1つの変数の1つのインスタンス化されたバインディング= 1つのチャンク）。

この自己参照サンクの動作は、次の適切な実装に組み込むことができることに注意してくださいfix。

-- | Find the least fixed point of @f@.  This implementation should produce
-- self-referential thunks, and thus run in constant space.
fix :: (a -> a) -> a
fix f = result
    where result = f result

cycle4 :: [a] -> [a]
cycle4 xs = fix (xs++)
于 2012-07-09T23:57:08.680 に答える