Непоследовательная функция монады в Haskell

Question

У меня возникли некоторые реальные проблемы с разработкой контрфункции Haskell's sequence функция, о которой мне говорит Google, еще не существует. Вот как это ведет себя:

ghci> sequence [Just 7, Just 8, Just 9]
Just [7,8,9]
ghci> sequence [getLine, getLine, getLine]
hey
there
stack exchange
["hey","there","stack exchange"] :: IO [String]

Моя проблема заключается в создании такой функции:

unsequence :: (Monad m) => m [a] -> [m a]

Так что он ведет себя так:

ghci> unsequence (Just [7, 8, 9])
[Just 7, Just 8, Just 9]
ghci> sequence getLine
hey
['h','e','y'] :: [IO Char] --(This would actually cause an error, but hey-ho.)

На самом деле я не знаю, возможно ли это, потому что в какой-то момент я бы избежал монады, но я начал, хотя и не знаю, как установить точку останова для этой рекурсивной функции:

unsequence m = (m >>= return . head) : unsequence (m >>= return . tail)

Я понимаю, что мне нужна точка останова, когда m здесь равно return []но не все монады Eq экземпляры, так как я могу это сделать? Это вообще возможно? Если так, то почему, а почему нет? Пожалуйста, скажи мне это.

Answer 1

Это действительно невозможно создать unsequence работать с использованием только монад. Причина в том, что:

1. Вы можете безопасно и легко создать монадическую структуру из значения, используя return,
2. Однако небезопасно удалять значение из монадической структуры. Например, вы не можете удалить элемент из пустого списка (т.е. функцию типа [a] -> a не безопасно).
3. Следовательно, у нас есть специальная функция (т.е. >>=), который безопасно удаляет значение из монадической структуры (если оно существует), обрабатывает его и возвращает другую безопасную монадическую структуру.

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

Предположим, у нас была функция extract :: Monad m => m a -> a который может "безопасно" удалить значение из монадической структуры. Мы могли бы затем реализовать unsequence следующее:

unsequence :: Monad m => m [a] -> [m a]
unsequence = map return . extract

Тем не менее, нет безопасного способа извлечь значение из монадической структуры. следовательно unsequence [] а также unsequence Nothing вернусь undefined,

Однако вы можете создать unsequence функция для структур, которые являются монадическими и комонадными. Comonad определяется следующим образом:

class Functor w => Comonad w where
    extract   :: w a -> a
    duplicate :: w a -> w (w a)
    extend    :: (w a -> b) -> w a -> w b

    duplicate = extend id
    extend f = fmap f . duplicate

Комонадная структура является противоположностью монадической структуры. Особенно:

1. Вы можете безопасно извлечь значение из запятой структуры.
2. Однако вы не можете безопасно создать новую комонадную структуру из значения, поэтому duplicate Функция безопасно создает новую comonadic структуру из значения.

Помните, что определение unsequence требуется оба return а также extract? Вы не можете безопасно создать новую comonadic структуру из значения (то есть comonadic структуры не имеют return). Следовательно unsequence Функция определяется следующим образом:

unsequence :: (Comonad m, Monad m) => m [a] -> [m a]
unsequence = map return . extract

что интересно sequence работает на просто монадических структурах. Таким образом, с помощью интуиции вы можете предположить, что unsequence работает на просто comonadic структурах. Однако это не так, потому что вам нужно сначала извлечь список из запятой структуры, а затем поместить каждый элемент списка в монадическую структуру.

Общая версия unsequence Функция преобразует структуру списка с комадонами в список структур с монадическими кодами:

unsequence :: (Comonad w, Monad m) => w [a] -> [m a]
unsequence = map return . extract

С другой стороны sequence Функция работает с простыми монадическими структурами, потому что вы просто складываете список монадических структур в структуру монадического списка, связывая все монады:

sequence :: Monad m => [m a] -> m [a]
sequence = foldr cons (return [])
    where cons mx mxs = do
        x  <- mx
        xs <- mxs
        return $ x:xs

Надеюсь, это поможет.

Answer 2

Вы не можете иметь unsequence :: (Monad m) => m [a] -> [m a], Проблема заключается в списках: вы не можете быть уверены, как элементы, которые вы собираетесь получить со списком, и это усложняет любое разумное определение unsequence,

Интересно, что если бы вы были абсолютно уверены на 100%, что список внутри монады бесконечен, вы могли бы написать что-то вроде:

unsequenceInfinite :: (Monad m) => m [a] -> [m a]
unsequenceInfinite x = fmap head x : unsequenceInfinite (fmap tail x)

И это будет работать!

Также представьте, что у нас есть Pair функтор валяется. Мы можем написать unsequencePair как

unsequencePair :: (Monad m) => m (Pair a) -> Pair (m a)
unsequencePair x = Pair (fmap firstPairElement x) (fmap secondPairElement x)

В общем, получается, что вы можете только определить unsequence для функторов со свойством, что вы всегда можете "сжать" два значения без потери информации. Бесконечные списки (в Haskell один из возможных типов для них Cofree Identity) являются примером. Pair Функтор это другое. Но не обычные списки или функторы, как Maybe или же Either,

в distributive пакет, есть класс типов, называемый Distributive который инкапсулирует это свойство. Ваш unsequence называется distribute там.