Создать функцию фильтра для монад в haskell - PullRequest
Новая
       14

Создать функцию фильтра для монад в haskell

3 голосов
/ 07 апреля 2019

Предположим, у нас есть функция фильтра.

filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]

Предположим, что наша функция a -> m Bool такова: 

p :: Integer -> Maybe Bool
p n | n > 0 = Just True
    | n < 0 = Just False
    | otherwise = Nothing

В примере m is Maybe.

Я хочу создать функцию filterM так, чтобы: 

filterM p [2,−4,1] = Just [2,1]

filterM p [2,0,−4,1] = Nothing

По существу этот фильтрM является фильтром, но для монад.

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

filterM p [] = pure []
filterM p (x : xs) | p x == Just True = x : (filterM p xs)
                   | p x == Just False = filterM p xs
                   | otherwise = Nothing

Во-первых, почему это не работает.Там написано Couldn't match type m with Maybe m is a rigid type variable. 

  Expected type: m Bool
  Actual type: Maybe Bool

В своей функции я жестко закодировал «Может быть» как m, но как мне сделать это более универсальным?

Я бы использовал нотацию do, ноэто не лучший вариант, так как есть рекурсия.

Ответы [ 2 ]

4 голосов
/ 07 апреля 2019

Есть две проблемы.Во-первых, вы дали сигнатуру типа: 

filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]

, а затем определили filterM с m, специализированным на Maybe (потому что вы используете Just и Nothing в своем определении).Когда Haskell определяет, что m должно быть Maybe, это приводит к ошибке.Тип m является «жестким» в том смысле, что он был предоставлен вами в сигнатуре типа, а жесткие типы должны оставаться общими;это конфликт, если они становятся менее полиморфными, чем указано.Вы можете сгенерировать подобное сообщение об ошибке, написав: 

badId :: a -> Int
badId x = x

Очевидно, a - это Int, и поэтому существует конфликт, что жесткий (определенный программистом) тип a был определен как соответствующийInt во время проверки типа.

Однако, даже если вы исправите сигнатуру типа: 

filterM :: (a -> Maybe Bool) -> [a] -> Maybe [a]
filterM p [] = pure []
filterM p (x : xs) | p x == Just True = x : (filterM p xs)
                   | p x == Just False = filterM p xs
                   | otherwise = Nothing

, вы все равно получите сообщение об ошибке.Вы смешиваете монадические действия и значения в своем коде.В выражении: 

x : filterM p xs

вы применяете оператор (:) :: b -> [b] -> [b] к типам a и Maybe [a], поэтому проверка типов не выполняется («Не удалось сопоставить ожидаемый тип Maybe [a]»).с действительным типом [a]. ")

Вам нужно заменить x : filterM p xs на что-то вроде: 

case filterM p xs of
    Nothing -> Nothing
    Just xs' -> Just (x : xs')
2 голосов
/ 07 апреля 2019

Ваша ошибка типа происходит из-за указания сигнатуры типа, которая является полиморфной (m), но является реализацией, которая специализируется на конкретном m (Maybe) - вы сказали, что средство проверки типов работает, forall m, но это не так.

Чтобы обобщить это, вам необходимо решить две другие незначительные проблемы: во-первых, вы не можете использовать общее монадическое условие в охране, только чистое условие. Во-вторых, вы не можете использовать оператор : для x и результат filterM, поскольку : чисто, но вы дали ему монадический аргумент.

Для монадической версии вы можете использовать do запись: 

filterM p [] = pure []
filterM p (x : xs) = do
  px <- p x  -- Run the condition
  if px
    then do
      xs' <- filterM p xs  -- Run the recursive action
      pure (x : xs')       -- Build the result
    else filterM p xs

Я бы использовал нотацию do, но это не лучший вариант, поскольку существует рекурсия.

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

Случай otherwise в вашем исходном коде неявно обрабатывается монадическими привязками; если p x возвращает Nothing для m ~ Maybe, тогда все вычисления вернут Nothing.

Если вы хотите избежать записи do, вы можете использовать комбинаторы монад / функторов напрямую: 

filterM p [] = pure []
filterM p (x : xs)
  = p x >>= \ px -> if px
    then (x :) <$> filterM p xs
    else filterM p xs

Хотя <$> (fmap) здесь лучше, я бы лично предпочел использовать do вместо >>= с лямбдой.

Это также можно несколько упростить, если учесть повторение filterM p и, поскольку p не изменяется в вызове на filterM, просто ссылается на него в вспомогательной функции. 

filterM p = go
  where
    go [] = pure []
    go (x : xs) = do
      px <- p x

      -- Or: if px then (x :) <$> go xs else go xs
      xs' <- go xs
      pure (if px then x : xs' else xs')
...