5

少しの間、次のことが良い考えだと思うとしましょう:

data Fold x y = Fold {start :: y, step :: x -> y -> y}

fold :: Fold x y -> [x] -> y

このスキームでは、lengthやなどの関数は、適切なオブジェクトを引数としてsum呼び出すことで実装できます。foldFold

ここで、巧妙な最適化のトリックを実行したいとします。特に、次のように書きたいとします。

unFold :: ([x] -> y) -> Fold x y

RULESのようなプラグマをルールするのは比較的簡単なはずですfold . unFold = id。しかし、興味深い質問は...実際に実装 unFoldできるかどうかです。

明らかRULESに、コードの元の意味を保持するかどうかに関係なく、任意のコード変換を適用するために を使用できます。unFoldしかし、型シグネチャが示唆することを実際に実行する実装を本当に書けるでしょうか?

4

4 に答える 4

12

いいえ、できません。証明: let

f :: [()] -> Bool
f[] = False
f[()] = False
f _ = True

空のリストを折りたたむと直接開始値を取得するため、最初に for をf' = unFold f持たなければなりません。次に、達成するstart f' = False必要があります。しかし、ここで を評価すると、再び呼び出しのみが得られます。したがって、 を満たすものは存在しません。□</p> step f' () False = Falsefold f' [()] = Falsefold f' [(),()]step f' () FalseFalsefold f' [(),()] ≡ Falsef[(),()] ≡ TrueunFold ffold $ unFold f ≡ f

于 2012-10-18T08:34:09.240 に答える
7

Foldできますが、それをやってのけるには、わずかな変更を加える必要があります。

リスト上のすべての関数は折り畳みとして表現できますが、これを実現するために追加の簿記が必要になる場合があります。Foldこの追加のコンテキスト情報を渡す追加の型パラメーターを型に追加するとします。

data Fold a c r = Fold { _start :: (c, r), _step :: a -> (c,r) -> (c,r) }

foldこれで、そのように実装できます

fold :: Fold a c r -> [a] -> r
fold (Fold step start) = snd . foldr step start

では、反対方向に行こうとするとどうなるでしょうか。

unFold :: ([a] -> r) -> Fold a c r

はどこcから来たのですか？関数は不透明な値であるため、関数を検査する方法や、関数が依存しているコンテキスト情報を知ることは困難です。それでは、少しごまかしましょう。「コンテキスト情報」をリスト全体にするので、一番左の要素に到達したら、関数を元のリストに適用し、以前の累積結果を無視できます。

unFold :: ([a] -> r) -> Fold a [a] r
unFold f = Fold { _start = ([], f [])
                , _step = \a (c, _r) -> let c' = a:c in (c', f c') }

悲しいことに、これは であるfold必要があるため、必ずしも で構成されるとは限りませcん[a]。c存在量化で隠すことでそれを修正しましょう。

{-# LANGUAGE ExistentialQuantification #-}
data Fold a r = forall c. Fold
  { _start :: (c,r)
  , _step :: a -> (c,r) -> (c,r) }

fold :: Fold a r -> [a] -> r
fold (Fold start step) = snd . foldr step start

unFold :: ([a] -> r) -> Fold a r
unFold f = Fold start step where
  start = ([], f [])
  step a (c, _r) = let c' = a:c in (c', f c')

さて、それは常に真実であるべきですfold . unFold = id. また、データ型の等価性の概念を緩和すると、次のFoldようにも言えますunFold . fold = id。Fold古いコンストラクタのように動作するスマート コンストラクタを提供することもできます。

makeFold :: r -> (a -> r -> r) -> Fold a r
makeFold start step = Fold start' step' where
  start' = ((), start)
  step' a ((), r) = ((), step a r)
于 2012-10-18T15:50:00.647 に答える
6

tl;dr:

結論1：できない

あなたが最初に求めたものは、少なくとも私が思いつくことができるあなたが望んでいたもののどのバージョンでも不可能です。(以下を参照してください。)データ型を変更して中間計算を保存できるようにすれば、問題ないと思いますが、それでも関数unFoldはかなり非効率的であり、巧妙な最適化トリックの議題に反するようです!

結論 2: 型を変更して回避しても、目的が達成されるとは思わない

リストアルゴリズムの最適化は、元の最適化されていない関数を使用してステップ関数を計算したという問題の影響を受け、おそらく複雑な方法で発生します。

関数には平等がないため、ステップを効率的なものに最適化することはできません。unFoldコンパイラではなく、人間が行う必要があると思います。

とにかく、元の質問に戻ります。

折りたたむことができます。unFold = id ?

いいえ。

isSingleton :: [a] -> Bool
isSingleton [x] = True
isSingleton _ = False

もし私たちが持っていunFold :: ([x] -> y) -> Fold x yたら、持っている必要foldSingletonがあるのと同じだったらunFold isSingleton

foldSingleton = Fold {start = False , step = ???}

where step はリストの要素を取り、結果を更新します。今isSingleton "a" == True、私たちは必要です

step False = True

そして、なぜならisSingleton "ab" == False、私たちは必要です

step True = False

これstep = notまでのところそうですが、isSingleton "abc" == False必要なことも

step False = False

([x] -> y)型の値で表現できない関数Fold x yが存在するため、 は総関数であるため、のunFold :: ([x] -> y) -> Fold x yような関数は存在しません。fold . unFold = idid

編集：

unFoldフォールドとしての表現を持つ関数でのみ作業することを期待していたので、これに納得していないことがわかりunFold.fold = idました。

展開できました。フォールド = id ?

いいえ。で取得できる機能だけに取り組み
たいと思っても、それは不可能だと思います。定義したと仮定して、質問に対処しましょうunFold([x] -> y)fold :: Fold x y -> ([x] -> y)

combine :: X -> Y -> Y
initial :: Y

folded :: [X] -> Y
folded = fold $ Fold initial combine

値の回復initialは簡単です: initial = folded []. の値を与える関数から の任意の値を組み合わせcombineた関数に移行する方法がないため、元の復元はそうではありません。YY

例として、X = Y = Int私が定義した場合

    combine x y | y < 0 = -10
                | otherwise = y + 1
    initial = 0

次に、正で使用するたびcombineに1を追加するだけで、初期値は0であるため、出力に関しては区別できません。が負になることはないので、関数を回復する関数を定義することも不可能であることに注意してください。これは、が単射ではないという事実に要約されます。type の異なる値を typeの同じ値に運びます。yyfoldedlengthfolded xsunFold :: ([x] -> y) -> Fold x ycombinefoldFold x y[x] -> y

したがって、私は 2 つのことを証明しました: if unFold :: ([x] -> y) -> Fold x ythen bothfold.unFold /= idと now alsounFold.fold /= id

リフォールディングされたときに同じ値を持っているのを見て、 を取得したFold 0 (\_ y -> y+1)か、Fold 0 combineから戻ったかをあまり気にしないので、これにも納得していないに違いありません! unFold foldedもう一度ゴールポストを絞りましょう。unFoldを介して関数を取得できるときはいつでも作業したいかもしれませんfoldが、結果を再度折りたたんだときに同じ関数が得られる限り、一貫性のない答えが得られないことを嬉しく思います。次の質問でそれを要約できます。

折りたたむことができます。展開します。折る＝折る？

つまり、 を介して取得できる一連の関数の ID にunFoldなるように定義できますか?fold.unFoldfold

stepサブリストの中間値に関する追加情報を保持せずに関数を計算するのは扱いやすい問題ではないため、これは不可能であると確信しています。

私たちが持っていたとしましょう

unFold f = Fold {start = f [], step = recoverstep f}

私たちは必要

recoverstep f x1 initial == f [x1]

したがって、x の Eq インスタンスがある場合 (警鐘を鳴らしてください!)、recoverstep は以下と同じ効果を持つ必要があります。

recoverstep f x1 y | y == initial = f [x1]

また、必要です

recoverstep f x2 (f [x1]) == f [x1,x2]

したがって、x の Eq インスタンスがある場合、recoverstep は次と同じ効果を持つ必要があります。

recoverstep f x2 y | y == (f [x1]) = f [x1,x2]

しかし、ここには大きな問題があります。変数x1は、この式の右辺で自由です。これは、論理的には、ステップ関数が使用されている値を知っていない限り、x でステップ関数が持つべき値を判断できないことを意味します。などの値を Fold データ型に格納して機能させる必要f [x1]があります。f [x1,x2]これが、 を定義できない理由の決定的な要因unFoldです。データ型 Fold を変更して、中間リストに関する情報を保存できるようにすれば、それが機能することはわかりますが、現状ではコンテキストを回復することは不可能です。

于 2012-10-18T08:50:29.290 に答える
1

ダンの答えに似ていますが、少し異なるアプローチを使用しています。アキュムレータを、最後に破棄される部分的な結果とペアにする代わりに、アキュムレータタイプから最終結果に変換する「後処理」関数を追加します。

同じ「チート」はunFold、後処理ステップのすべての作業を実行します。

{-# LANGUAGE ExistentialQuantification #-}

data Fold a r = forall c. Fold
  { _start  :: c
  , _step   :: a -> c -> c
  , _result :: c -> r }

fold :: Fold a r -> [a] -> r
fold (Fold start step result) = result . foldr step start

unFold :: ([a] -> r) -> Fold a r
unFold f = Fold [] (:) f

makeFold :: r -> (a -> r -> r) -> Fold a r
makeFold start step = Fold start step id
于 2012-10-19T01:58:49.527 に答える