Expression Problem

https://haskell.e-bigmoon.com/posts/2019/09-09-extensible-ast.html

Expression Problem とは何か？

既存のコードを変更 (再コンパイル) せずに、新しい関数とデータの両方を追加することは難しいという問題です。

ベースとなるコードは以下の通りです。

data Expr
  = Constant Double
  | BinaryPlus Expr Expr

stringify :: Expr -> String
stringify (Constant c) = show c
stringify (BinaryPlus lhs rhs) =
  stringify lhs <> " + " <> stringify rhs

evaluate :: Expr -> Double
evaluate (Constant c) = c
evaluate (BinaryPlus lhs rhs) = evaluate lhs + evaluate rhs

解決方法

プログラミング言語ごとに解決策がいくつもあります。

型クラス

データコンストラクタを型として別々に定義します。

module Base where

data Constant = Constant Double
  deriving (Show)

data BinaryPlus lhs rhs = BinaryPlus lhs rhs
  deriving (Show)

このままではデータがバラバラなので、型クラスを使ってまとめます。

Base.hs
class Expr e

instance Expr Constant
instance (Expr lhs, Expr rhs) => Expr (BinaryPlus lhs rhs)

{-
data Expr
  = Constant Double
  | BinaryPlus Expr Expr
-}

操作 evaluate を型クラスのメソッドとして定義します。

module Eval where

import Base

class (Expr e) => Eval e where
  evaluate :: e -> Double

instance Eval Constant where
  evaluate (Constant x) = x

instance (Eval lhs, Eval rhs) => Eval (BinaryPlus lhs rhs) where
  evaluate (BinaryPlus lhsx rhsx) = evaluate lhsx + evaluate rhsx
  
{-
evaluate :: Expr -> Double
evaluate (Constant c) = c
evaluate (BinaryPlus lhs rhs) = evaluate lhs + evaluate rhs
-}

操作 stringify を型クラスのメソッドとして定義します。

module Stringify where

import Base

import Text.Printf

class (Expr e) => Stringify e where
  stringify :: e -> String

instance Stringify Constant where
  stringify (Constant x) = show x

instance (Stringify lhs, Stringify rhs) => Stringify (BinaryPlus lhs rhs) where
  stringify (BinaryPlus lhsx rhsx) = printf "(%s + %s)" (stringify lhsx) (stringify rhsx)

参考リソース

PreviousTheseNext[WIP] Free Theorem

Last updated