Очепятки в книге по функциональному программированию

transform (Lam x (Var y)) | x == y
  = i transform (Lam x e)
                          | (not . free x) e
  = App k (transform e) transform (Lam x l@(Lam y e))
                          | free x e
  = transform (Lam x (transform l))

data Exp v = Lit v | Exp v :+ Exp v | Exp v :* Exp v deriving ( Eq, Show )

eval :: Num v => Exp v -> v
eval (Lit v) = v
eval (x :+ y) = eval x + eval y
eval (x :* y) = eval x * eval y

test = do
  let x = (Lit 1 :+ Lit 2) :* (Lit 3 :+ Lit 4)
  print x
  print $ eval x

q = Lam "x"
		(Lam "y"
			(Lam "z"
				(App (Var "x")
					 (App (Var "y")
						  (Var "z")))))
w = transform q

infixl 6 :$
infixr 5 :?

data T v = V v | T v :$ T v | v :? T v | S | K | I deriving Show

free :: Eq v => v -> T v -> Bool
free a (V b) = a == b
free a (x :$ y) = free a x || free a y
free a (_ :? x) = free a x
free _ _ = False

toSKI :: Eq v => T v -> T v
toSKI (x :$ y) = toSKI x :$ toSKI y
toSKI (a :? x) | not $ free a x = K :$ toSKI x
toSKI (a :? V b) = if a == b then I else K :$ V b
toSKI (a :? b :? x) | free a x = toSKI $ a :? toSKI (b :? x)
toSKI (a :? x :$ y) = S :$ toSKI (a :? x) :$ toSKI (a :? y)
toSKI x = x

main :: IO ()
main = do
  let q = "x" :? "y" :? "z" :? V "x" :$ V "y" :$ V "z"
  print q
  print $ toSKI q

transform (Lam x (Var y)) | x == y
  = i transform (Lam x e)
                          | (not . free x) e

transform (Lam x (Var y)) | x == y
  = i
transform (Lam x e) | (not . free x) e

%w[** / * + -].map{|o|String.send(:define_method,o){|n|"(#{o=='**'??^:o} #{self} #{n})"}}
puts eval gets.gsub(/\w/,'?\0').gsub ?^,'**'

<   = i transform (Lam x e)
>   = i
> transform (Lam x e)

<   = App k (transform e) transform (Lam x l@(Lam y e))
>   = App k (transform e)
> transform (Lam x l@(Lam y e))

#include <vector>
#include <iostream>

template <typename Value>
struct Exp {
    virtual ~Exp() {}
    virtual Value eval() const = 0;
    virtual std::string show() const = 0;
};

template <typename Value>
class Lit : public Exp<Value> {
    const Value value;
public:
    Lit(Value const& value_) : value(value_) {}
    Value eval() const { return value; }
    std::string show() const { return "lit(" + std::to_string(value) + ")"; }
};

template <typename Value>
class Add : public Exp<Value> {
    using E = Exp<Value>;
    const E &x, &y;
public:
    Add(E const& x_, E const& y_) : x(x_), y(y_) {}
    Value eval() const { return x.eval() + y.eval(); }
    std::string show() const { return "add(" + x.show() + ", " + y.show() + ")"; }
};

template <typename Value>
struct Mul : public Exp<Value> {
    using E = Exp<Value>;
    const E &x, &y;
public:
    Mul(E const& x_, E const& y_) : x(x_), y(y_) {}
    Value eval() const { return x.eval() * y.eval(); }
    std::string show() const { return "mul(" + x.show() + ", " + y.show() + ")"; }
};

template <typename Value>
class GarbagePool {
    std::vector<Exp<Value>*> garbage_pool;
public:
    ~GarbagePool() { for (auto e : garbage_pool) delete e; }
    Exp<Value>& collect(Exp<Value>* e) { garbage_pool.push_back(e); return *e;   }
};

int main() {
    GarbagePool<int> gp;
    using Exp = Exp<int>;
    auto lit = [&gp](int x) -> Exp& { return gp.collect(new Lit<int>(x)); };
    auto mul = [&gp](Exp const& x, Exp const& y) -> Exp& {
        return gp.collect(new Mul<int>(x, y));
    };
    auto add = [&gp](Exp const& x, Exp const& y) -> Exp& {
        return gp.collect(new Add<int>(x, y));
    };
    auto &exp = mul(add(lit(1), lit(2)), add(lit(3), lit(4)));
    std::cout << exp.show() << " => " << exp.eval() << std::endl;
}

transform (Lam x (App e1 e2)) = App (App s (transform (Lam x e1))) (transform (Lam x e2))

transform (Lam x l@(Lam y e)) | free x e = transform (Lam x (transform l))

#include <iostream>

enum selector {Lit, Plus, Mult};
struct expr
{
  Selector t;
  expr *value1, *value2;
  int value;
  expr(int val) { t = Lit; value = val; }
  expr(selector _t, expr *_v1, expr *_v2) { t = _t; value1 = _v1; value2 = _v2 };
  string show() 
  { 
     case (t)
     {
        Lit: return "Lit(" + to_string(value) + ")";
        Plus: return "Plus(" + value1.show() + "," +value2.show() + ")";
        Mult: return "Mult(" + value1.show() + "," +value2.show() + ")";
     }
  }
  ~expr() { delete value1; delete value2; }
}

expr* plus(expr *a, expr* b) { new expr(Plus, a, b); }
expr* mult(expr *a, expr* b) { new expr(Mult, a, b); }
int eval(expr *a)
{
   case (a->t)
   {
      Lit: return a->value;
      Plus: return eval(a->value1) + eval(a->value2);
      Mult: return eval(a->value1) * eval(a->value2);
   }
}

int main()
{
   expr *x = new expr(Mult, new expr Plus(1, 2), new expr Plus(3, 4));
   cout << x.show() << end;
   cout << eval(x) << endl;
}

#include <iostream>
#include <string>

using namespace std;
enum selector {Lit, Plus, Mult};
struct expr
{
  selector t;
  expr *value1, *value2;
  int value;
  expr(int val) { t = Lit; value = val; }
  expr(selector _t, expr *_v1, expr *_v2) { t = _t; value1 = _v1; value2 = _v2; }
  ~expr() { delete value1; delete value2; }
};

ostream& operator<< (ostream& os, expr& s) {
    switch (s.t)
    {
        case Lit: return os << "Lit("  << s.value << ")";
        case Plus: return os << "Plus(" << *s.value1 << "," << *s.value2 << ")";
        case Mult: return os << "Mult(" << *s.value1 << "," << *s.value2 << ")";
    }
}

expr* plus(expr *a, expr* b) { new expr(Plus, a, b); }
expr* mult(expr *a, expr* b) { new expr(Mult, a, b); }
int eval(expr *a)
{
   switch (a->t)
   {
      case Lit: return a->value;
      case Plus: return eval(a->value1) + eval(a->value2);
      case Mult: return eval(a->value1) * eval(a->value2);
   }
}

int main()
{
   expr x(Mult, new expr(Plus, new expr(1), new expr(2)),
                new expr(Plus, new expr(3), new expr(4)));
   cout << x << endl;
   cout << eval(&x) << endl;
}

enum selector {LIT, PLUS, MUL};
struct expr {
    const selector type;
    const int lit_val;
    const shared_ptr<expr> oper_val1;
    const shared_ptr<expr> oper_val2;

    static shared_ptr<expr> lit(int i)
    {
        return shared_ptr<expr>(new expr(i));
    }
    static shared_ptr<expr> plus(shared_ptr<expr> a, shared_ptr<expr> b)
    {
        return shared_ptr<expr>(new expr(PLUS, a, b));
    }

    static shared_ptr<expr> mul(shared_ptr<expr> a, shared_ptr<expr> b)
    {
        return shared_ptr<expr>(new expr(MUL, a, b));
    }

private:
    expr(int value)
        : type(LIT), lit_val(value)
    {}
    expr(selector t, const shared_ptr<expr> & value1, const shared_ptr<expr> & value2)
        : type(t), lit_val(0), oper_val1(value1), oper_val2(value2)
    {}
};

string show(const shared_ptr<expr> & a)
{
    switch (a->type) {
    case LIT:
        return "lit(" + to_string(a->lit_val) + ")";
    case PLUS:
        return "plus(" + show(a->oper_val1) + "," + show(a->oper_val2) + ")";
    case MUL:
        return "mul(" + show(a->oper_val1) + "," + show(a->oper_val2) + ")";
    }
}

int eval(const shared_ptr<expr> & a)
{
    switch (a->type) {
    case LIT:
        return a->lit_val;
    case PLUS:
        return eval(a->oper_val1) + eval(a->oper_val2);
    case MUL:
        return eval(a->oper_val1) * eval(a->oper_val2);
    }
}

int main()
{
    auto x = expr::mul(
        expr::plus(expr::lit(1), expr::lit(2)),
        expr::plus(expr::lit(3), expr::lit(4))
    );
    cout << show(x) << endl;
    cout << eval(x) << endl;
}