Często potrzebuję dodać pola do narzędzia ADT, które zapamiętuje tylko niektóre zbędne informacje. Ale nie zrozumiałem całkowicie, jak to zrobić ładnie i skutecznie.

Najlepszym sposobem na pokazanie problemu jest zrobienie przykładu. Załóżmy, że pracujemy z nieokreślonymi terminami lambda:

type VSym = String

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

Od czasu do czasu musimy obliczyć zbiór wolnych zmiennych danego terminu:

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)

Wkrótce zdajemy sobie sprawę, że powtarzane obliczeniafv są wąskim gardłem naszej aplikacji. Chcielibyśmy jakoś dodać go do typu danych. Lubić:

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

Ale to sprawia, że ​​definicja jest brzydka. Prawie(Set VSym) zajmuje więcej miejsca niż cała reszta. Ponadto przerywa dopasowywanie wzorców we wszystkich używanych funkcjachLambda. Co gorsza, jeśli później zdecydujemy się dodać jakieś inne pole do zapamiętania, będziemy musieli ponownie przepisać wszystkie wzorce.

Jak zaprojektować ogólne rozwiązanie umożliwiające łatwe i dyskretne dodawanie takich pól pamięci? Chciałbym osiągnąć następujące cele:

Thedata definicja powinna wyglądać jak najbliżej oryginału, aby była łatwa do odczytania i zrozumiała.Dopasowania wzorców również powinny pozostać proste i czytelne.Dodanie nowego pola zapamiętywania później nie powinno łamać istniejącego kodu, w szczególności:nie łamać istniejących wzorów,nie wymagać zmian, gdy używana była funkcja, którą chcemy zapamiętać (jak kod, który używałfv w tym przykładzie).

Opiszę moje obecne rozwiązanie: Aby zachowaćdata dopasowania definicji i wzorców, jak najmniej zaśmiecone, zdefiniujmy:

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

gdzie dane do zapamiętania są definiowane oddzielnie:

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

Następnie prosta funkcja, która pobiera zapamiętaną część:

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

(Można to wyeliminować za pomocą nazwanych pól. Ale wtedymuszą wymienić wszystkie pozostałe pola także.)

To pozwala nam wybrać konkretne części z pamięci, zachowując ten sam podpisfv jak wcześniej:

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

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

Na koniec deklarujemy tych inteligentnych konstruktorów:

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

Teraz możemy efektywnie pisać rzeczy, które łączą dopasowanie wzorców z odczytaniem zapamiętanych pól, takich jak

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

To wydaje się rozwiązywać:

Dopasowywanie wzorców jest nadal całkiem rozsądne.Jeśli dodamy nowe pole zapamiętywania, nie zakłóci to istniejącego kodu.Jeśli zdecydujemy się zapamiętać funkcję z podpisemLambda -> Something możemy łatwo dodać go jako nowe pole zapamiętywania.

Co nadal nie podoba mi się w tym projekcie:

Thedata definicja nie jest taka zła, ale wciąż umieszczanamemo wszędzie go zaśmieca.Musimy mieć inteligentne konstruktory do konstruowania wartości, ale używamy konstruktorów regularnych do dopasowywania wzorców. To nie jest takie złe, po prostu dodajemy jeden_, ale posiadanie tego samego podpisu do konstruowania i dekonstruowania byłoby miłe. PrzypuszczamWidoki lubSynonimy synonimów rozwiąże to.Obliczanie zapamiętanych pól (wolnych zmiennych, głębokości) jest ściśle powiązane z inteligentnymi konstruktorami. Ponieważ rozsądnie jest założyć, że te zapamiętane funkcje będą zawszekatamorfizmy, Wierzę, że można to w pewnym stopniu rozwiązać za pomocą narzędzi takich jakpakiet punktów stałych.

Jakieś pomysły, jak to poprawić? A może są lepsze sposoby rozwiązania tego problemu?