I would like to use Python. And when it comes to monads, Maybe is famous.
Maybe is relatively easy to understand and practical in various languages, so some people implement it by themselves. I think it's going to happen. But, I think it's better to understand from the State monad I have found an article like that.
So I'm going to implement the State monad. Try to make a calculator for addition, subtraction, multiplication and division using stack in Haskell Haskell State Monad (1)-Imitate State 6th State monad for using local "state" I read something like that to raise awareness.
I can't deny the feeling that there are so many existing articles. Besides, the explanation including the reference article It is concrete and easy to understand. However, for that reason, in the implementation part of the Ikansen stack I put too much effort into it, and I felt that it was difficult to grasp the essence of State.
So, here as a more abstract mechanism by reimplementing it yourself using a slightly different language Aim to get a grasp of the State monads.
So, here, without thinking about anything extra, refer to the Haskell implementation. For the time being, I would like to learn the essence of the State monad by porting it to Python as it is. Python is a dynamic type language, but if it seems difficult to understand, let's add type annotations with timely comments.
Let's take a look at Haskell's definition.
newtype State s a = State { runState :: s -> (a, s) }
instance Monad (State s) where
return a = State $ \s -> (a, s)
m >>= k = State $ \s -> let
(a, s') = runState m s
in runState (k a) s'
Looking at the definition, State seems to be a monad with the function s-> (a, s) inside.
s is State, isn't it?
In the tuple of the return value, a on the left is the result of the change, and s on the right is the state after the change is made.
From a procedural linguistic point of view, this one gives a strange impression!
By the way, for those who are not familiar with Haskell grammar,
Haskell declares lambda expressions in the form \ argument-> expression.
Also, the keyword let is a let expression, and variables are bound under let.
ʻIn` It is like returning the following expression.
I also want Python (I made it http://qiita.com/hatchinee/items/1face0ffd5466de1ad97).
And there is another definition of a function that gets and rewrites the state. This is declared as a typeclass called MonadState.
class (Monad m) => MonadState s m | m -> s where
get :: m s
put :: s -> m ()
instance MonadState s (State s) where
get = State $ \s -> (s, s)
put s = State $ \_ -> ((), s)
Haskell power is low, so what is a type class or instance is an OOP? And various questions It disappears when it floats (* myuon_myon explained in the comments. Thanks!) Translate the function part with no mind.
Let's start with State for the time being.
class State(object):
def __init__(self, a):
''' private '''
self.run_state = a
@classmethod
def ret(_, a):
''' return
'''
return State(lambda s: (a, s))
def bind(self, func):
''' >>=
'''
def _(a):
v, st = self.run_state(a)
return func(v).run_state(st)
return State(_)
def __rshift__(self, func):
''' define >> as bind '''
return self.bind(func)
runState is a self.run_state member
Since return is a reserved word in Python, declare it as a class method called ret.
>> = is called >> because it looks like a bind method or something similar.
Make it available in the operator.
I feel that >> was used by another Monad operator, so if you think it's dangerous, you can use another one.
class MonadState(object):
@classmethod
def get(_):
''' get = State $ \s -> (s, s)
'''
return State(lambda s: (s, s))
@classmethod
def put(_, a):
''' put s = State $ \_ -> ((), s)
'''
return State(lambda s: (None, a))
Monad State. I tried to put the definition in Haskell in the comment, but it can be implemented almost as it is. Now let's use these implementations to see if state rewriting and retrieving works.
>>> (MonadState.put(12) >> (lambda _: \
MonadState.get())).run_state(13)
(12, 12)
>>> (MonadState.put(12) >> (lambda _: \
MonadState.get() >> (lambda i: \
MonadState.put(i * 2)))).run_state(13)
(None, 24)
I think it will work if you run it as a prompt or doctest.
The State monad is probably by abstracting the procedure by synthesizing a function and giving it a state. I thought it was a mechanism that could get results or side effects on the condition.
It may take some time to understand because the behavior of get and put and the composition part in bind are complicated. What happens when you try to implement it yourself or create something using State I think you will be able to feel it in your heart.
Now that you've somehow felt it in your heart, let's make something nice with the State monad. Speaking of stacks, I will make a reverse Polish calculator.
For the time being, define an auxiliary function that converts a character string into an operator.
from operator import add, sub, div, mul, concat
_OP_HOLDER = {
'+': add,
'-': sub,
'*': mul,
'/': div,
}
def _op(st):
op = _OP_HOLDER[st]
def _(x1, x2):
'''Since it is difficult to control the pop order, invert here'''
print x2, st, x1
return [op(x2, x1)]
return _
def _concat(xs, ys):
print xs, ys
return concat(xs, ys)
def _is_valid_operator(v):
return v in ['+', '-', '*', '/']
Next, implement the push or calculation part to the calculator.
class Calculator(object):
@classmethod
def push(_, val):
if _is_valid_operator(val):
return \
MonadState.get() >> (lambda x:
MonadState.put(
_concat(
x, _op(val)(x.pop(), x.pop()))))
else:
return \
MonadState.get() >> (lambda x:
MonadState.put(_concat(x, [val])))
@classmethod
def run(_, stk):
_, ret = stk.run_state([])
return ret.pop()
It's troublesome, so the pop part directly accesses the internal list.
Let's test it.
if __name__ == '__main__':
C = Calculator
print '1 2 + 4 5 + *'
calc = \
C.push(1) >> (lambda _:
C.push(2) >> (lambda _:
C.push('+') >> (lambda _:
C.push(4) >> (lambda _:
C.push(5) >> (lambda _:
C.push('+') >> (lambda _:
C.push('*')))))))
assert C.run(calc) == (1 + 2) * (4 + 5)
'''
1 2 + 4 5 + *
[] [1]
[1] [2]
1 + 2
[] [3]
[3] [4]
[3, 4] [5]
4 + 5
[3] [9]
3 * 9
[] [27]
Should be printed like!
'''
print '\n5 4 3 - +'
calc = \
C.push(5) >> (lambda _:
C.push(4)) >> (lambda _:
C.push(3)) >> (lambda _:
C.push('-')) >> (lambda _:
C.push('+'))
assert C.run(calc) == (5 + 4 - 3)
print '\n6 2 + 5 3 - 2 * /'
calc = \
C.push(6) >> (lambda _:
C.push(2) >> (lambda _:
C.push('+') >> (lambda _:
C.push(5) >> (lambda _:
C.push(3) >> (lambda _:
C.push('-') >> (lambda _:
C.push(2) >> (lambda _:
C.push('*') >> (lambda _:
C.push('/')))))))))
assert C.run(calc) == (6 + 2) / ((5 - 3) * 2)
How is it? I'm new to implementing a Reverse Polish Notation Calculator, so I'm not sure. I think it's working nicely.
The operation part works with or without higher-order functions. If you use a higher-order function, it seems that you can also perform calculations (such as sum) using the aggregate of the results of each operation.
It doesn't seem to be directly practical for writing Python, but it was fun to be a brain teaser. Thank you for your support.
If you like this, please also check it out (Summary of articles about Python's black magic coding I've written so far -about-python)))
Recommended Posts