Применить функцию к подструктурам автоматически - PullRequest
Новая
       21

Применить функцию к подструктурам автоматически

6 голосов
/ 08 февраля 2012

Предположим, я пишу функцию "замены" для типа данных абстрактного синтаксического дерева: 

data Term = Id String
          | If Term Term Term
          | Let String Term Term
          ...

subst :: String -- name of identifier to replace
      -> Term   -- term to replace the identifier with
      -> Term   -- body in which to perform the replacements
      -> Term
subst identifier term = go
  where go (Id id') = if identifier == id' then term else Id id'
        go (If t1 t2 t3) = If (go t1) (go t2) (go t3)
        go (Let id' term' body) = Let id' (go term') (go body)
        ...

(Игнорировать проблемы с тенями).Обратите внимание, как утомительно писать ветку If.Я должен сопоставить образец, назвав 3 части, а затем восстановить If, применяя go к каждой из 3 частей явно.Для Let я должен сопоставить образец, назвав 3 части, и реконструировать Let, применяя go к соответствующим 2 частям в явном виде.Есть ли более простой (бессмысленный?) Способ написать это, не объясняя каждую деталь?

1 Ответ

13 голосов
/ 08 февраля 2012

Лучшим подходом здесь является использование общего типа данных программирования, которое было точно разработано для таких задач AST-ходьбы.Вот пример использования стандартной библиотеки SYB : 

{-# LANGUAGE DeriveDataTypeable #-}

import Data.Generics

data Term = Id String
          | If Term Term Term
          | Let String Term Term
          deriving (Eq, Show, Typeable, Data)

subst :: String -- name of identifier to replace
      -> Term   -- term to replace the identifier with
      -> Term   -- body in which to perform the replacements
      -> Term
subst identifier term = everywhere (mkT go)
  where go (Id id') = if identifier == id' then term else Id id'
        go x = x

Это прямо выражает преобразование (в данном случае применение функции go к любому дочернему элементу типа Term).) следует применять ко всему дереву снизу вверх.Это не только намного более кратко, но и тот же код продолжает работать независимо от того, сколько конструкций добавлено в Term, пока базовая схема рекурсии остается прежней.

...