Копируется ли состояние при каждой операции над монадой состояния в Haskell?

Question

[Даниил Колесниченко]

Допустим, есть пример реализации частного случая монады State на Python — стека с операциями push и pop:

from collections import namedtuple

Stack = namedtuple('Stack', ('value', 'stack'))

Stack.bind = lambda self, fn: fn(self.value, self.stack)

def pop(_, stack):
    return Stack(stack[-1], stack[:-1])

def push(value):
    def inner(_, stack):
        return Stack(value, stack + [value])
    return inner

print(Stack(0, [])
    .bind(push(1))
    .bind(push(2))
    .bind(push(3))
    .bind(pop)
    .stack
)    # [1, 2]

Получается, что при каждой операции копируется весь стек. В Haskell можно было бы добавлять элемент в начало, тогда будет копироваться только ссылка на хвост, но суть не меняется — если бы там был словарь, то при каждой операции, получается, копируется весь словарь. По идее, производительность должна быть гораздо хуже, чем в императивных языках, где ничего копировать каждый раз не надо. Правильно ли я всё понял? Можно ли с этим что-то сделать?

Answer 1

[Александр Ручкин]

Копируется, только надо учитывать ленивость и чистоту Хаскеля.
Если взять обычный список и класть ему в голову - ничего не надо будет копировать, так как добавление головы не требует копирования хвоста, новый список будет просто ссылаться на хвост. Удаление головы (т.е. взятие хвоста) тоже не требует создавать копий.
Если же вы будете в качестве состояния использовать какой-либо строгий тип данных, да с unboxed членами, тот да, будет копироваться.
Надо учитывать так же и другую вещь: накопление thunk'ов. Например, если состояние - это число, и вы миллион раз сделаете modify (+1), по факту там будет лежать отложенное вычисление на миллион прибавлений единиц, что будет кушать память. Потому есть строгая монада state, а также modify', который форсирует применение переданной функции.

Answer 2

[ZloyEngineer]

Пример, что вы привели на питоне -- это stack, а не state.

Монада State не предоставляет функциональности стека, она лишь предоставляет возможность хранения некой переменной. С точки зрения человека с головой набитой императивными тараканами это выглядит как полное копирование. Тем ни менее это не так и все зависит от программиста, нужно ли ему таскать за собой весь список или нет решает сам программист.

Например, stack-пример, приведенный выше можно реализовать (используя классическую императивную реализацию) с помощью State монады так:

import Control.Monad.State

pop :: State [a] a
pop = do
  h <- head <$> get
  modify tail
  return h

push :: a -> State [a] ()
push = modify . (:)

print $ runState (mapM_ push [1 :: Int ,2,3,4]>>pop) []

Тем ни менее ленивые вычисления с слабые на голову конструкторы сильно меняют логику выполнения программы, если смотреть с классической императивной позиции.

Answer 3

[nirvimel]

Несмотря на то, что State внутри тоже стек, надо разделить саму State и структуру данных, которая через него протаскивается:

from collections import namedtuple

State = namedtuple('State', ('fx', 'previous'))
State.unit = staticmethod(lambda value=None: State(lambda: value, None))
State.bind = lambda self, fx: State(fx, self)
State.get = lambda self: self.fx(self.previous.get()) if self.previous else self.fx()

push = lambda value: lambda stack: (value, stack) if stack else value
pop = lambda stack: stack[1] if isinstance(stack, tuple) else stack
toList = lambda stack: toList(stack[1]) + [stack[0]] if isinstance(stack, tuple) else [stack]

print (State.unit()
       .bind(push(1))
       .bind(push(2))
       .bind(push(3))
       .bind(pop)
       .bind(toList)
       .get()) # [1, 2]

toList - довольно медленная, приведена только для примера.