Áp dụng một chức năng để tự động Cấu kiện nhỏ dùng

Question

Giả sử tôi viết một "thay thế" chức năng trên một kiểu dữ liệu cây cú pháp trừu tượng:

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) 
     ... 

(Bỏ qua vấn đề shadowing). Lưu ý rằng việc viết chi nhánh If tẻ nhạt đến mức nào. Tôi phải khớp mẫu, đặt tên cho 3 phần, và sau đó tạo lại một If áp dụng go cho từng phần trong số 3 phần một cách rõ ràng. Đối với Let, tôi phải đối sánh mẫu, đặt tên cho 3 phần và xây dựng lại Let áp dụng go cho 2 phần có liên quan một cách rõ ràng. Có cách nào dễ dàng hơn (pointfree?) Để viết điều này mà không phải đánh vần từng chi tiết?

Answer 1

Cách tiếp cận tốt nhất ở đây là sử dụng lập trình datatype-generic, được thiết kế chính xác cho các tác vụ đi bộ AST như thế này. Dưới đây là một ví dụ, bằng cách sử dụng tiêu chuẩn SYB thư viện:

{-# 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 

này trực tiếp bày tỏ rằng việc chuyển đổi (trong trường hợp này, việc áp dụng các chức năng go cho bất kỳ đứa trẻ của loại Term) nên được áp dụng cho toàn bộ cây trong một đáy theo cách thức. Không chỉ có điều này ngắn gọn hơn nhiều, nhưng cùng một mã tiếp tục hoạt động bất kể có bao nhiêu cấu trúc được thêm vào Term, miễn là lược đồ đệ quy cơ bản vẫn giữ nguyên.