The title is unclear.
There is an essay about functional programming (language).
I read it because there is a great translated article.
[Algebraic Data Types] expressed in OCaml in this essay (http://en.wikipedia.org/wiki/%E4%BB%A3%E6%95%B0%E7%9A%84%E3% 83% 87% E3% 83% BC% E3% 82% BF% E5% 9E% 8B) and examples of pattern matching are introduced.
- Phenotypes and evaluators in OCaml
type 'a expr = | True | False | And of 'a expr * 'a expr | Or of 'a expr * 'a expr | Not of 'a expr | Base of 'a let rec eval eval_base expr = let eval' x = eval eval_base x in match expr with | True -> true | False -> false | Base base -> eval_base base | And (x,y) -> eval' x && eval' y | Or (x,y) -> eval' x || eval' y | Not x -> not (eval' x)
It also provides a comparison of what happens if you implement the equivalent in Java. I think that many non-functional programming languages do not support algebraic data types (direct sum types) as a language. Python is one such language. Consider replacing the Java code introduced in the article with Python.
First is the implementation of the evaluator. Since the Java code in the original article only defines the interface and does not introduce the implementation, we also use * ABCMeta * and * abstractmethod * for the interface, and the implementation is appropriate.
3.4
from abc import ABCMeta, abstractmethod
class Evaluator(metaclass=ABCMeta):
@abstractmethod
def evaluate(self, value): pass
class MyEvaluator(Evaluator):
def evaluate(self, value):
return bool(value)
Now let's move on to defining Boolean expressions and the functions that evaluate them. Like the * Evaluator * above, it inherits an interface-like thing called * Expr * and defines each expression as an object.
3.4
class Expr(metaclass=ABCMeta):
@abstractmethod
def eval(self, evaluator): pass
class True_(Expr):
def eval(self, evaluator):
return True
class False_(Expr):
def eval(self, evaluator):
return False
class Base(Expr):
def __init__(self, value):
self.value = value
def eval(self, evaluator):
return evaluator.evaluate(self.value)
class And(Expr):
def __init__(self, expr1, expr2):
self.expr1 = expr1
self.expr2 = expr2
def eval(self, evaluator):
return self.expr1.eval(evaluator) and self.expr2.eval(evaluator)
class Or(Expr):
def __init__(self, expr1, expr2):
self.expr1 = expr1
self.expr2 = expr2
def eval(self, evaluator):
return self.expr1.eval(evaluator) or self.expr2.eval(evaluator)
class Not(Expr):
def __init__(self, expr):
self.expr = expr
def eval(self, evaluator):
return not self.expr.eval(evaluator)
Is it like this?
Let's set aside the details and run it to see if it works.
3.4
>>> from sample1 import *
>>> evaluator = MyEvaluator()
>>> true, false = True_(), False_()
>>> true.eval(evaluator)
True
>>> And(Base(3), false).eval(evaluator)
False
I think it looks more like a * eval * function-like call than this.
3.4
>>> from operator import methodcaller
>>> eval_ = methodcaller('eval', evaluator)
>>> eval_(Not(true))
False
>>> eval_(Or(And(Base(3), false), Not(false)))
True
・ ・ ・
Probably not very important to do (I'm just doing it to test the implementation).
I was able to express the direct sum of algebraic data types using interfaces (like things) and inheritance. Now let's take a look at Ocaml's definition of algebraic data types.
type 'a expr = | True | False | And of 'a expr * 'a expr | Or of 'a expr * 'a expr | Not of 'a expr | Base of 'a
Original article(translation)Quoted from
Direct sum formulas are shown by pipes that separate different declarations. Of these declarations, for example True and False, are single tags and are virtually the same as elements of Java and C enums. Others, such as And and Not, have data that is tied together, and that data can vary. This type actually contains both direct sum and direct product types because the And and Or parts contain tuples. A type consisting of a combination of product and sum layers is common in OCaml and is a powerful idiom.
Rather than expressing it in a class using inheritance**|** (pipe)There is no dispute that the expression described in is much more concise.
Furthermore, direct sum types are enumerated types(enum)But it is said that it can be expressed, so let's try that as well. Python 3.From 4 to the standard libraryenumModules have been added. standardenumBecause it cannot be expressed conciselyextenumI'm using the extension, but don't worry, it's not essential.
3.4
from extenum import ConstantSpecificEnum
class Expr(ConstantSpecificEnum):
TRUE = 1
FALSE = 2
BASE = 3
AND = 4
OR = 5
NOT = 6
@overload(TRUE)
def eval(self, evaluator, *args):
return True
@overload(FALSE)
def eval(self, evaluator, *args):
return False
@overload(BASE)
def eval(self, evaluator, *args):
return evaluator.evaluate(args[0])
@overload(AND)
def eval(self, evaluator, *args):
return evaluator.evaluate(args[0]) and evaluator.evaluate(args[1])
@overload(OR)
def eval(self, evaluator, *args):
return evaluator.evaluate(args[0]) or evaluator.evaluate(args[1])
@overload(NOT)
def eval(self, evaluator, *args):
return not evaluator.evaluate(args[0])
OneenumNow that we've defined an object that corresponds to the expression in the class, it might be a bit better than the inheritance example above.
3.4
>>> from sample2 import *
>>> Expr.TRUE.eval(evaluator)
True
>>> Expr.AND.eval(evaluator,
... Expr.BASE.eval(evaluator, 3),
... Expr.FALSE.eval(evaluator))
...
False
If you hide the evaluator because it looks redundant,
3.4
>>> true = Expr.TRUE.eval(evaluator)
>>> false = Expr.FALSE.eval(evaluator)
>>> from functools import partial
>>> Base = partial(Expr.BASE.eval, evaluator)
>>> And = partial(Expr.AND.eval, evaluator)
>>> Or = partial(Expr.OR.eval, evaluator)
>>> Not = partial(Expr.NOT.eval, evaluator)
>>> Not(true)
False
>>> Or(And(Base(3), false), Not(false))
True
It became easier to see like that(It's easier to test if it works) 。
In Hateb's comment, there was a comment that it is not fair to express and compare the characteristic points of functional programming languages with procedural programming languages. I think it makes sense, but I praise one in contrast.(Despise)Rather, I thought the original article was wonderful as an opportunity to think about how different programming paradigms would be used for the same purpose.
For example, I'm not familiar with functional programming languages, so it's still easier to understand what the code intends to do in Java than in OCaml. And from the same reason, I wrote it in Python.
If the expression is concise, it's better and programming(language)I thought it was a good example to realize that the paradigm of and the expressiveness of the code are closely related.
Recommended Posts