Как return работает в контексте Monad в Haskell
Почему следующее, учитывая, что экземпляр RegModule определяет свой возврат как: return a = RegModule (\_s _i d -> return (a, 0, d)), не возвращает [((c, i+1, d), Int, d)], и почему второе выражение case не нужно записывать с return []:
scanChar :: RegModule d Char
scanChar = RegModule (\s i d ->
case drop i s of
(c:cs) -> return (c, i+1, d)
[] -> []
)
В МВЕ:
import qualified Data.Set as S
import Control.Monad
type CharSet = S.Set Char
data RE =
RClass Bool CharSet
newtype RegModule d a =
RegModule {runRegModule :: String -> Int -> d -> [(a, Int, d)]}
instance Monad (RegModule d) where
return a = RegModule (\_s _i d -> return (a, 0, d))
m >>= f =
RegModule (\s i d -> do (a, j, d') <- runRegModule m s i d
(b, j', d'') <- runRegModule (f a) s (i + j) d'
return (b, j + j', d''))
instance Functor (RegModule d) where fmap = liftM
instance Applicative (RegModule d) where pure = return; (<*>) = ap
scanChar :: RegModule d Char
scanChar = RegModule (\s i d ->
case drop i s of
(c:cs) -> return (c, i+1, d)
[] -> []
)
regfail :: RegModule d a
regfail = RegModule (\_s _i d -> []
)
regEX :: RE -> RegModule [String] ()
regEX (RClass b cs) = do
next <- scanChar
if (S.member next cs)
then return ()
else regfail
runRegModuleThrice :: RegModule d a -> String -> Int -> d -> [(a, Int, d)]
runRegModuleThrice matcher input startPos state =
let (result1, pos1, newState1) = head $ runRegModule matcher input startPos state
(result2, pos2, newState2) = head $ runRegModule matcher input pos1 newState1
(result3, pos3, newState3) = head $ runRegModule matcher input pos2 newState2
in [(result1, pos1, newState1), (result2, pos2, newState2), (result3, pos3, newState3)]
Вы имеете в виду, что этот return (c, i+1, d) использует instance Monad [] ? В таком случае, как он узнает, что нужно использовать instance Monad [], а не instance Monad (RegModule d), у которого также есть функция return a?
Из-за вывода типа: для проверки типа RegModule (\s i d -> ...) требуется, чтобы ... имел тип [(a, Int, d)]. Таким образом, обе ветви case return (c, i+1, d) и [] должны иметь такой тип. Это, в свою очередь, вызывает выбор экземпляра Monad [] для return.
@Piskator return всегда использует ожидаемый тип, чтобы определить, какой Monad экземпляр использовать. В этом случае return (c, i+1, d) не появляется в контексте, где он должен создавать RegModule, потому что он используется внутри конструктора RegModule. Конструктор RegModule принимает функцию String -> Int -> d -> [(a, Int, d)], а return используется для создания возвращаемого значения списка такой функции (ранняя часть \s i d -> уже позаботилась о том, чтобы поместить нас внутрь функции, принимающей 3 параметра).
@Piskator: да, return (c, i+1, d) в этом контексте просто [(c, i+1, d)]
Ответы 1
Это вопрос вывода типа. В коде:
scanChar :: RegModule d Char
scanChar = RegModule (\s i d ->
case drop i s of
(c:cs) -> return (c, i+1, d)
[] -> []
)
конструктор RegModule справа имеет тип:
RegModule :: (String -> Int -> d -> [(a, Int, d)]) -> RegModule d a
Поскольку scanChar имеет сигнатуру типа RegModule d Char, Haskell объединяет типы RegModule d Char (слева) с RegModule d a (справа), что приводит к унификации переменной типа a с Char. Следовательно, ожидаемый тип функции, передаваемой конструктору RegModule:
String -> Int -> d -> [(Char, Int, d)]
Обратите внимание, что до сих пор мы рассматривали только сигнатуру типа для scanChar и тип конструктора RegModule. Ничто из различных экземпляров для RegModule не использовалось.
В любом случае, анонимная лямбда \s i d -> ... унифицируется с этим типом, поэтому аргументы s, i и d должны иметь тип String, Int и d соответственно, как и следовало ожидать из их имен, а тело должно иметь тип [(Char, Int, d)]. Поскольку тело анонимной лямбды представляет собой выражение case, каждое выражение в правой части одного из случаев должно иметь один и тот же тип, [(Char, Int, d)]. Итак, у нас есть:
return (c, i+1, d) :: [(Char, Int, d)] -- for the first case
и:
[] :: [(Char, Int, d)] -- for the second case
Функция return полиморфна с типом (Monad m) => t -> m t, поэтому, чтобы унифицировать это конкретное выражение return с его типом, Haskell унифицирует m с функтором списка [] и t с типом аргумента, переданного в (c, i+1, d), а именно (Char, Int, d). Это инстанцирует return к типу монады []:
return :: t -> [t]
и список для элементов типа (Char, Int, d) в частности:
return :: (Char, Int, d) -> [(Char, Int, d)]
Итак, используется функция return для монады списка, и, учитывая ее определение, вы можете заменить код на:
...
(c:cs) -> [(c, i+1, d)]
...
и это имело бы такое же значение.
С другой стороны, если [] в правой части последнего случая заменить на return [], компилятор попытается унифицировать сигнатуру общего типа для return:
return :: (Monad m) => t -> m t
объединяя тип аргумента t с типом пустого списка [] :: [u], давая равенство типов:
t ~ [u]
для некоторого u, при этом тип выражения return [] унифицируется с ожидаемым типом на основе приведенного выше вывода типа, а именно m t, давая равенства типов:
m ~ []
t ~ (Char, Int, d)
Поскольку равенство типов [(Char, Int, d)] несовместимо с равенством типов t ~ [u], это будет ошибкой типа:
Return.hs:29:18-19: error:
• Couldn't match expected type: (Char, Int, d)
with actual type: [a0]
В конце концов, ни один из приведенных выше выводов типов не использует тип t ~ (Char, Int, d) для return монады.
ваш
returnне используетinstance Monad (RegModule d), он используетinstance Monad [], список, поэтомуreturnпереносит значение в список.