Преобразование функции трансформатора потока в Мили автомата в Haskell

Question

я работать с потоками:

data Stream a = Cons a (Stream a) 

В частности, поток функции трансформаторные:

f :: Stream a -> Stream b 

Я хотел бы сделать автомат Мили из такой функции :

data Mealy a b = Mealy (a -> (b, Mealy a b)) 

Есть ли способ написать такую ​​функцию?

toMealy :: (Stream a -> Stream b) -> Mealy a b 

Я не могу найти способ. Хотя другой способ работает легко:

toStreamTransformer :: Mealy a b -> Stream a -> Stream b 

Возможно, мне не хватает чего-то тривиального?

Answer 1

В этом ответе используется абстракция Stream, предоставляемая пакетом streaming. Эта абстракция:

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

Представьте у вас есть функция, как:

module Main where 

import Streaming 
import Streaming.Internal (Stream(Effect,Step,Return)) 
import Streaming.Prelude 

transformation :: Monad m => Stream (Of Int) m r -> Stream (Of String) m r 
transformation = undefined -- your code here 

transformation изменяет поток Int значений в поток String значений. Он является полиморфным на базе монады, что означает, что само преобразование является чистым. Он является полиморфным по типу возврата r, что означает, что преобразование всегда исчерпывает поток источника.

Теперь мы пишем эти вспомогательные определения:

data Feed a = Input a | EOF 

trickster :: Monad m => Stream (Of a) (Stream ((->) (Feed a)) m)()   
trickster = do 
    r <- Effect (Step (Return . Return)) -- request a `Feed a` value 
    case r of 
     Input a -> Step (a :> trickster) 
     EOF  -> Return() 

trickster немного странно. На внешнем уровне это поток, который производит значения a.Но внизу мы имеем что-то вроде монады Free (->) (здесь также реализовано с Stream), которое принимает значения a и испускает их на внешнем уровне.

Что произойдет, если мы применяем trickster к transformation, а затем объединить два Stream слоя с помощью функции unseparate?

machine :: Stream (Sum (Of String) ((->) (Feed Int))) Identity()   
machine = unseparate (transformation trickster) 

Мы можем продвигать через machine используя inspect функцию

inspect :: (Functor f, Monad m) => Stream f m r -> m (Either r (f (Stream f m r))) 

Вот страшный тип:

ghci> :t runIdentity (inspect machine) 
runIdentity (inspect machine) 
    :: Either 
     () 
     (Sum 
      (Of String) 
      ((->) (Feed Int)) 
      (Stream (Sum (Of String) ((->) (Feed Int))) Identity())) 

Это в основном означает, что на данном этапе машина либо завершается (но реализация trickster гарантирует, что он никогда этого не сделает, если мы не пройдем EOF), или он производит String или требуется ввести значение Int.

(Мы могли бы обойтись без unseparate, но процесс отслаивания двух Stream слоев была бы более запутанной.)

(Также см пост в блоге Programmatic translation to iteratees from pull-based code Пол Chiusano за оригинальную идею позади этого кода .)

Answer 2

Если Вы предполагаете, что поток трансформатор передается toMealy является «детерминированным», то вы можете получить Мили машины запускается, на входе a, передавая a : e : e : ... в потоке трансформатор (где e = error "input stream transformer is not deterministic"), и выводите первый элемент b выходного потока. Затем измените свой трансформатор потока, чтобы добавить a к его вводу и отбросить первый элемент (предположительно b) его вывода и рекурсии.

Или, если вы предпочитаете, вы можете использовать вход a : a : a : ...; то вы получите полную функцию, которая не определяет, является ли вход детерминированным, но создает машину Мили, которая только генерирует исходный трансформатор потока, когда он есть.

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