Непоследовательность Функция Monad в Haskell

Question

У меня возникли проблемы с конструированием функции Haskell sequence, о которой говорит Hoogle, еще не существует. Это, как он ведет себя:

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, которая могла бы “ safely ” удалить значение из монадической структуры. Тогда мы могли бы реализовать 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 

comonadic структура противоположность монадической структуры. В частности:

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

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

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

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

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

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.