16

多くの場合、冗長な情報のみをメモするフィールドをADTに追加する必要があります。しかし、私はそれをうまくそして効率的に行う方法を完全には理解していません。

問題を示す最良の方法は、例を作成することです。型指定されていないラムダ用語を使用していると仮定します。

type VSym = String

data Lambda = Var VSym 
            | App Lambda Lambda
            | Abs VSym Lambda

そして時々、項の自由変数のセットを計算する必要があります。

fv :: Lambda -> Set VSym
fv (Var v)    = Set.singleton v
fv (App s t)  = (fv s) `Set.union` (fv t)
fv (Abs v t)  = v `Set.delete` (fv t)

すぐに、の繰り返し計算がアプリケーションのボトルネックであることに気付きfvます。どういうわけかデータ型に追加したいと思います。好き：

data Lambda1 = Var (Set VSym) VSym
             | App (Set VSym) Lambda Lambda
             | Abs (Set VSym) VSym Lambda

しかし、それは定義をかなり醜くします。ほとんど(Set VSym)他のすべてよりも多くのスペースを取ります。さらに、を使用するすべての関数でパターンマッチングを破りますLambda。さらに悪いことに、後で他のメモ化フィールドを追加することにした場合は、すべてのパターンを再度書き直す必要があります。

このようなメモ化フィールドを簡単かつ目立たないように追加できる一般的なソリューションを設計するにはどうすればよいですか？次の目標を達成したいと思います。

  1. data定義は、読みやすく理解しやすいように、可能な限り元の定義に近づける必要があります。
  2. パターンの一致もシンプルで読みやすいものにする必要があります。
  3. 後で新しいメモ化フィールドを追加しても、特に次のような既存のコードが破損することはありません。
    • 既存のパターンを壊さないために、
    • fvメモ化する関数が使用された場所（この例で使用されたコードなど）を変更する必要はありません。

現在の解決策について説明します。data定義とパターンの一致をできるだけ乱雑にしないために、次のように定義しましょう。

data Lambda' memo = Var memo VSym 
                  | App memo (Lambda' memo) (Lambda' memo)
                  | Abs memo VSym (Lambda' memo)
type Lambda = Lambda' LambdaMemo

ここで、メモ化するデータは個別に定義されます。

data LambdaMemo = LambdaMemo { _fv :: Set VSym, _depth :: Int }

次に、メモ化された部分を取得する単純な関数：

memo :: Lambda' memo -> memo
memo (Var c _)   = c
memo (App c _ _) = c
memo (Abs c _ _) = c

（これは、名前付きフィールドを使用することで排除できます。ただし、他のすべてのフィールドにも名前を付ける必要があります。）

fvこれにより、メモ化から特定の部分を選択し、以前と同じ署名を維持できます。

fv :: Lambda -> Set VSym
fv = _fv . memo

depth :: Lambda -> Int
depth = _depth . memo

最後に、これらのスマートコンストラクターを宣言します。

var :: VSym -> Lambda
var v = Var (LambdaMemo (Set.singleton v) 0) v

app :: Lambda -> Lambda -> Lambda
app s t = App (LambdaMemo (fv s `Set.union` fv t) (max (depth t) (depth s))) s t

abs :: VSym -> Lambda -> Lambda
abs v t = Abs (LambdaMemo (v `Set.delete` fv t) (1 + depth t)) v t

これで、パターンマッチングとメモ化されたフィールドの読み取りを組み合わせたものを効率的に書くことができます。

canSubstitute :: VSym -> Lambda -> Lambda -> Bool
canSubstitute x s t
  | not (x `Set.member` (fv t))
      = True -- the variable doesn't occur in `t` at all
canSubstitute x s t@(Abs _ u t')
  | u `Set.member` (fv s)
      = False
  | otherwise
      = canSubstitute x s t'
canSubstitute x s (Var _ _)
      = True
canSubstitute x s (App _ t1 t2)
      = canSubstitute x s t1 && canSubstitute x s t2

これは解決するようです：

  • パターンマッチングはまだかなり合理的です。
  • 新しいメモ化フィールドを追加しても、既存のコードが中断されることはありません。
  • 関数を署名付きでメモ化することにした場合、Lambda -> Somethingそれを新しいメモ化フィールドとして簡単に追加できます。

このデザインについて私がまだ気に入らない点：

  • data定義はそれほど悪くはありませんが、それでもどこにでも配置するmemoとかなり乱雑になります。
  • 値を作成するにはスマートコンストラクターが必要ですが、パターンマッチングには通常のコンストラクターを使用します。これはそれほど悪くはありません。1つ追加するだけです_が、構築と分解に同じ署名を付けると便利です。ビューまたはパターンシノニムがそれを解決すると思います。
  • メモ化されたフィールド（自由変数、深さ）の計算は、スマートコンストラクターと緊密に結合されています。これらのメモ化された関数は常にカタモルフィズムであると想定するのが合理的であるため、これは、fixpointパッケージなどのツールによってある程度解決できると思います。

それを改善する方法はありますか？または、そのような問題を解決するためのより良い方法はありますか？

4

1 に答える 1

2

結果をADT自体にキャッシュするのではなく、関数で単純な古いメモ化を使用することで、すべての目標を達成できると思います。ほんの数週間前、私はstable-memoパッケージをリリースしました。これはここで役立つはずです。あなたの基準を確認して、私たちはこれよりも良いことはできないと思います：

  1. データ定義はまったく変更されません。
  2. パターンマッチングも変わりません。
  3. メモ化された関数をさらに作成するという理由だけで、既存のコードを変更する必要はありません。
    • 既存のパターンが壊れることはありません。
    • 既存のメモ化された関数が壊れることはありません。

使い方はとても簡単です。メモ化する関数に適用memoするだけで、再帰呼び出しであっても、メモ化されたバージョンの関数をどこでも使用するようにしてください。質問で使用した例の書き方は次のとおりです。

import Data.StableMemo

type VSym = String

data Lambda = Var VSym 
            | App Lambda Lambda
            | Abs VSym Lambda

fv :: Lambda -> Set VSym
fv = memo go
  where
    go (Var v)   = Set.singleton v
    go (App s t) = fv s `Set.union` fv t
    go (Abs v t) = v `Set.delete` fv t
于 2012-11-09T16:20:38.217 に答える