Haskellの再帰

Question

私は与えられた式の変数にカウンターを追加することに取り組んでいて、次のテストケースを持ってきた

：私は試してみて、解決策を見つけるためにパターンマッチングと再帰を使用している

。私はちょっと立ち往生しましたが、元の変数をリストに追加してからリストを使用して出力する変数名を決定しようとしましたが、正しく実装する方法を理解できず、出力に1すべての変数の最後まで

私はこのより良い/簡単な解決策があるのでしょうか？

これまでの私の試み：

add :: Expr -> Expr 
add T = T 
add (Var x) = Var (x ++ show (check2(check x))) 
add (And e1 e2) = And (add e1) (add e2) 
add (Not e1) = Not (add e1) 

check :: Variable -> [Variable] 
check p = [p] 

check2 :: [Variable] -> Int 
check2 p = length (union p p) 

Answer 1

あなたは数字に変数名をマッピングした環境を維持する必要があります。

add :: Expr -> Expr 
add expr = fst $ addWithEnv emptyEnv expr 
    where 
    emptyEnv = [] 
    addWithEnv env (And e1 e2) 
     = case addWithEnv env e1 of 
      (e1', env') -> 
       case addWithEnv env' e2 of 
       (e2', env'') -> (And e1' e2', env'') 
    addWithEnv env (Var name) 
     = case lookup name env of 
      Just k -> -- stopping here,it's homework 

ような何か私はあなたが記入するために、私は十分に残してきた期待し

更新：あなたの試みで

、あなたはすでに見てきたどの変数を追跡していません、すべての変数が最初のように見え、毎回 '1'が追加されます。ナンバリング項目はステートフルな計算です。以前に見た変数に以前の番号を割り当て、次に見られない変数を割り当てる番号を知るためには、どの変数がこれまでに見られたのかの記録を持たなければなりません。だからあなたはその記録を労働者の周りに運ばなければならない。もしあなたがすでにMonadクラスについて知っていて、それを使う方法があれば、Stateモナドを使ってそれを暗黙に持ち歩くことができます。それ以外の場合は明示的に持ち歩かなければなりません。その後、addは、最初に空の状態（番号/名前の変更が始まる前に、変数はまだ見られません）で作業者を呼び出すラッパーになります。その後、ワーカーは指定された式のサブ式を調べ、変数の名前を変更し、新しい変数に遭遇したときの状態を更新します。

は、したがって、上記のスケッチでは、我々は

addWithEnv :: [(String,Int)] -> Expr -> (Expr, [(String,Int)]) 

を持って、我々は状態を変異させることができないので、私たちは、名前を変更した表現と一緒に新しい状態を返すことがあります。今、あなたは

addWithEnv env T = ?? 
addWithEnv env (Var name) = ?? 
addWithEnv env (Add e1 e2) = ?? 
addWithEnv env (Not e) = ?? 

もちろんのT場合には名前の変更を行わず、環境を更新しない、結果は式の種類ごとにしなければならないかを定義する必要があります。 A Varが以前に見られたかのいずれかであり、その場合、環境は変更されないままであり、そうでない場合、環境に追加される。 Not eは、環境への影響が同じで、環境に及ぼす影響は最初にe1、次にe2となり、eとなり、And e1 e2は、最初にe1となる組み合わせ効果があります。