Каковы хорошие оболочки для переноса изменения состояния в haskell?

Question

Я пытаюсь реализовать простой бэкэнд FRP, для моих собственных интересов.

Я решил использовать чистые функции: так, нет ввода-вывода в ядре. Реализация основана на преобразователе сигнала.

Я уже попробовал два способа:

newtype SF a b = SF { listen :: [a] -> [b] }

https://gist.github.com/Heimdell/9675964

а также

newtype SF a b = SF { run :: a -> (b, SF a b) }

https://gist.github.com/Heimdell/9675964 (ошибочно назван, извините)

Оба способа позволяют сделать fold/integrate :: (a -> b -> b) -> b -> SF a b комбинатор для интеграции сигналов.

У обоих способов есть проблема: кажется невозможным создать действительный экземпляр ArrowApply/Monad.

• Stream-way: у нас есть список пар (arrow, x) - или же, unzipред, пара списков (arrows, xs),

  • Если мы будем map head к результату zipWith ($) их, мы потеряем мутацию стрелы.
  • если мы сделаем head arrows Слушать xs, мы заморозим состояние первой взятой стрелки.

• Явный путь состояния:

  instance ArrowApply Behaviour where
      app =
          Behaviour $ \(bf, a) ->
              let (bf1, c) = bf `runBehaviour` a
  
              in (app, c)
  

  Здесь нужно как-то правильно вводить bf1 в app возвращается, что невозможно (и на самом деле (const bf1 *** id) выдает некорректное поведение, аналогичное второму из другой реализации.

Есть ли возможный способ сделать SF который позволяет экземпляр ArrowApply?

PS: Потоковый путь имеет утечку памяти в ArrowChoice, когда ветвь долго не используется. Пока я не могу это исправить. Можно ли когда-нибудь сделать версию без утечек?

PPS: Если нужно время, он мог бы сжать его с вводом.

Answer 1

Я не могу найти ни одного возможного экземпляра, который не просто отбрасывает состояние внутреннего контейнера. Это неудивительно, поскольку возврат из чистой функции, связанной с данными, должен возвращать одно и то же при каждом вызове ввода, независимо от того, был ли он вызван ранее, на что вы намекаете в своих комментариях.

Само собой

Единственный Monad В случаях, когда я могу придумать оба, отбрасывать последующие состояния для внутреннего контейнера.

instance Monad (SF e) where
    return a = SF . const $ (a, return a)
    (>>=) sa f = SF go
        where
            go e = 
                let
                    (a, sa') = run sa e
                    sb = f a
                    (b, _) = run sb e
                in
                    (b, sa' >>= f)

или же

join :: SF e (SF e a) -> SF e a
join ssa = SF go
    where
        go e =
            let
                (sa, ssa') = run ssa e
                (a, _) = run sa e
            in
                (a, join ssa')

Это можно выразить более кратко, используя экземпляр Monad для функций

instance Monad (SF e) where
    return a = SF . const $ (a, return a)
    (>>=) sa f = SF {
        run =
            do
                (a, sa') <- run sa
                (b, _) <- run (f a)
                return (b, sa' >>= f)
    }

Мы можем искать в другом месте что-то немного другое.

Функция Монад Экземпляр

Ваш newtype SF e a = SF { run :: e -> (a, SF e a) } очень близко к функции от e в a, Для экземпляра Monad для функций единственный разумный >>= это передать аргумент как внутренней, так и внешней функции. Это то, что мы уже придумали. Посмотрим, сможем ли мы придумать что-нибудь еще.

StateT

Ваш код чем-то похож на монадный преобразователь StateT, применяемый к экземпляру Monad для функций. К сожалению, это не дает того, что мы ищем.

Рассмотрим следующее (монадный трансформатор StateT):

newtype StateT s m a = StateT { runStateT :: s -> m (a, s)}

Применяется к типу ((->) e) функции, которая принимает аргумент `е.

StateT s ((->) e) a имеет единственный конструктор StateT { runStateT :: s -> e -> (a, s) },

Это отличается от вашего типа тем, что необходимо предоставить начальное состояние, и состояние отслеживается явно, а не уже включено в возвращаемое следующее значение. Давайте посмотрим, что Monad экземпляр для этого будет. StateT"s Monad пример

instance (Monad m) => Monad (StateT s m) where
    return a = state $ \s -> (a, s)
    m >>= k  = StateT $ \s -> do
        ~(a, s') <- runStateT m s
        runStateT (k a) s'

state f = StateT (return . f)

В сочетании с экземпляром для (->) e

instance Monad ((->) e) where
    return = const
    (>>=) x y z = y (x z) z

Мы получили бы следующее, где do сваливает работу на экземпляр для ((->) e)

instance Monad (StateT s ((->) e) where
    return a = StateT (const . (\s -> (a, s)))
    m >>= k  = StateT $ \s e ->
        let (a, s`) = runStateT m s e
        in runStateT (k a) s` e

Это выглядит совсем по-другому. Мы не теряем историю любого государства. Здесь происходит то, что состояние внутреннего контейнера передается ему из внешнего контейнера, и два контейнера должны иметь одинаковый тип, чтобы это состояние могло работать. Это совсем не то, что мы хотим.

Что-то новое

Что произойдет, если мы попытаемся сделать что-то вроде StateT от вашего типа? Мы хотели бы иметь возможность передать в типе (->) e и получить структуру, как у вас. Мы сделаем то, что называется SFT m a такой, что SFT ((-> e) a имеет ту же структуру, что и SF e a,

newtype SF  e a = SF  { run   :: e -> (a, SF  e a)
newtype SFT m a = SFT { unSFT :: m    (a, SFT m a) }

Мы можем заменить тип, сделанный, применяя SFT в (->) e) за SF применительно к e

SF        e  a -- is replaced by
SFT ((->) e) a

Это имеет один конструктор

SF  { run   :: e -> (a, SF        e  a) }
SFT { unSFT :: e -> (a, SFT ((->) e) a) }

Это не дает нового понимания, единственное Monad Пример, который я могу придумать, потому что он почти идентичен оригинальному.

instance Monad m => Monad (SFT m) where
    return a = SFT . return $ (a, return a)
    (>>=) sa f = SFT {
        unSFT =
            do
                (a, sa') <- unSFT sa
                (b, _) <- unSFT (f a)
                return (b, sa' >>= f)
    }