Haskell: FP versus OO

Martin Sulzmann

Reflection: OO versus FP

Let's discuss:

Haskell/FP

OO:

See the Expression Problem.

Haskell evaluator for simplified expression language

data Exp = Val Int | Plus Exp Exp 

eval :: Exp -> Int
eval (Val v) = v
eval (Plus e1 e2) =  eval e1 + eval e2

-- 1 + 3
e2 :: Exp
e2 = Plus (Val 1) (Val 3)

OO-style evaluator for simplified expression language

// C++
class Exp {
 public:
  Exp() {};
  virtual int eval() = 0;
};

class IntExp : public Exp {
  int val;
  public:
  IntExp(int _val) { val = _val; }
  int eval() { return val;}
};

class PlusExp : public Exp {
  Exp* e1;
  Exp* e2;
  public:
  PlusExp(Exp* _e1, Exp* _e2) { e1 = _e1; e2 = _e2; }
  int eval() { return e1->eval() + e2->eval(); }
};

OO versus Haskell/FP

class MultExp : public Exp {
  Exp* e1;
  Exp* e2;
  public:
  MultExp(Exp* _e1, Exp* _e2) { e1 = _e1; e2 = _e2; }
  int eval() { return e1->eval() * e2->eval(); }
};
simp :: Exp -> Exp
simp (Plus (Val 0) e) = simp e
simp (Plus e1 e2) = Plus (simp e1) (simp e2)
simp x = x

Pattern matching syntax in OO languages

Haskell pattern matching:

Example: Simplification

simp :: Exp -> Exp
simp (Plus (Val 0) e) = simp e
simp (Plus e1 e2) = Plus (simp e1) (simp e2)
simp x = x

Expressing the above via 'plain' OO (classes and virtual methods) leads to clumsy code.

Of course, we can mimic pattern matching in OO languages (e.g. via run-time type information)

Evaluator based on run-time type information

// Would be "instanceOf" in Java
struct Exp {
  // We can only dynamic cast over polymorphic types
  virtual void bogus() {}
};

struct IntExp : public Exp {
public:
  int val;
  IntExp(int _val) { val = _val; }
};

struct PlusExp : public Exp {
public:
  Exp* e1;
  Exp* e2;
  PlusExp(Exp* _e1, Exp* _e2) { e1 = _e1; e2 = _e2; }
};


int eval(Exp* e) {
  if(IntExp *i = dynamic_cast<IntExp*>(e)) {
    return i->val;
  }
  else if (PlusExp *p = dynamic_cast<PlusExp*>(e)) {
    return (eval(p->e1) + eval(p->e2));
  }
  else {
    cout << "pattern matching failure \n";
  }

}

Evaluator based on user-provided "type" information

typedef enum {
  IntKind,
  PlusKind
} ExpKind;

struct Exp {
  ExpKind kind;
};

struct IntExp : public Exp {
public:
  int val;
  IntExp(int _val) { kind = IntKind; val = _val; }
};

struct PlusExp : public Exp {
public:
  Exp* e1;
  Exp* e2;
  PlusExp(Exp* _e1, Exp* _e2) { kind = PlusKind; e1 = _e1; e2 = _e2; }
};


int eval(Exp* e) {
  if(e->kind == IntKind) {
    IntExp* i = static_cast<IntExp*>(e);
    return i->val;
  }
  else if (e->kind == PlusKind) {      
    PlusExp *p = static_cast<PlusExp*>(e);
    if (p->e1->kind == IntKind) {
      IntExp *i = static_cast<IntExp*>(p->e1);
      // 0 + e --> e
      if(i->val == 0) 
    return eval(p->e2);
      // (e1 + e2) -> eval each subpart
      else return eval(p->e1) + eval(p->e2);
    }
    else  return (eval(p->e1) + eval(p->e2));
  }
  else {
    cout << "pattern matching failure \n";
  }

}

OO versus Haskell/FP Revisited