Странная ошибка типа в выражении let на Haskell - в чем проблема?

Question

Сегодня я столкнулся с разочаровывающим чем-то в Haskell.

Вот что произошло:

1. Я написал функцию в ghci и дал ей сигнатуру типа
2. ghci пожаловался на тип
3. Я удалил сигнатуру типа
4. ghci принял функцию
5. Я проверил выведенный тип
6. выводимый тип был точно таким же, как и тип, который я пытался дать
7. Я был очень огорчен
8. Я обнаружил, что могу воспроизвести проблему в любом выражении let
9. Скрежетзубов;решил проконсультироваться с экспертами по SO

---

Попытка определить функцию с сигнатурой типа:

Prelude Control.Monad> let myFilterM f m = do {x <- m; guard (f x); return x} :: (MonadPlus m) => (b -> Bool) -> m b -> m b

<interactive>:1:20:
    Inferred type is less polymorphic than expected
      Quantified type variable `b' is mentioned in the environment:
        m :: (b -> Bool) -> m b -> m b (bound at <interactive>:1:16)
        f :: (m b -> m b) -> Bool (bound at <interactive>:1:14)
      Quantified type variable `m' is mentioned in the environment:
        m :: (b -> Bool) -> m b -> m b (bound at <interactive>:1:16)
        f :: (m b -> m b) -> Bool (bound at <interactive>:1:14)
    In the expression:
          do { x <- m;
               guard (f x);
               return x } ::
            (MonadPlus m) => (b -> Bool) -> m b -> m b
    In the definition of `myFilterM':
        myFilterM f m
                    = do { x <- m;
                           guard (f x);
                           return x } ::
                        (MonadPlus m) => (b -> Bool) -> m b -> m b

Определяетсяфункция без сигнатуры типа, проверил выведенный тип:

Prelude Control.Monad> let myFilterM f m = do {x <- m; guard (f x); return x}
Prelude Control.Monad> :t myFilterM 
myFilterM :: (MonadPlus m) => (b -> Bool) -> m b -> m b

Использовал функцию для хорошего блага - она ​​работала правильно:

Prelude Control.Monad> myFilterM (>3) (Just 4)
Just 4
Prelude Control.Monad> myFilterM (>3) (Just 3)
Nothing

---

Мое лучшее предположение относительно того, что происходит:
аннотации типа как-то не очень хорошо работают с выражениями let, когда есть do-block.

Для бонусных баллов:
есть ли в стандартном дистрибутиве Haskell функция, которая делает это?Я был удивлен, что filterM делает что-то совсем другое.

Answer 1

Проблема в приоритете оператора типа (::).Вы пытаетесь описать тип myFilterM, но на самом деле вы делаете следующее:

ghci> let myFilterM f m = (\
        do {x <- m; guard (f x); return x} \
        :: \
        (MonadPlus m) => (b -> Bool) -> m b -> m b)\
      )

(обратная косая черта вставлена ​​только для удобства чтения, недопустимый синтаксис ghci)

DoВы видите проблему?Я получаю ту же проблему для чего-то простого, например

ghci> let f x = x + 1 :: (Int -> Int)
<interactive>:1:15:
    No instance for (Num (Int -> Int))
      arising from the literal `1'
    Possible fix: add an instance declaration for (Num (Int -> Int))
    In the second argument of `(+)', namely `1'
    In the expression: x + 1 :: Int -> Int
    In an equation for `f': f x = x + 1 :: Int -> Int

Решение состоит в том, чтобы прикрепить сигнатуру типа к соответствующему элементу:

ghci> let f :: Int -> Int ; f x = x + 1
ghci> let myFilterM :: (MonadPlus m) => (b -> Bool) -> m b -> m b; myFilterM f m = do {x <- m; guard (f x); return x}

А для бонусных баллов вы хотите mfilter ( Google - ваш друг ).

Answer 2

Вероятно, это просто проблема синтаксиса аннотации типов и приоритета привязки.Если вы напишите свой пример как

let myFilterM :: (MonadPlus m) => (b -> Bool) -> m b -> m b; myFilterM f m = do {x <- m; guard (f x); return x} 

, то GHCi даст вам пять и отправит вас в путь.

Answer 3

Я не знаю, какой компилятор вы используете, но на моей платформе (GHC 7.0.3) я получаю простое несоответствие типов:

$ ghci
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> :m +Control.Monad
Prelude Control.Monad> let myFilterM f m = do {x <- m; guard (f x); return x} :: (MonadPlus m) => (b -> Bool) -> m b -> m b

<interactive>:1:30:
    Could not deduce (t1 ~ ((b1 -> Bool) -> m1 b1 -> m1 b1))
    from the context (MonadPlus m)
      bound by the inferred type of
               myFilterM :: MonadPlus m => t -> t1 -> (b -> Bool) -> m b -> m b
      at <interactive>:1:5-100
    or from (MonadPlus m1)
      bound by an expression type signature:
                 MonadPlus m1 => (b1 -> Bool) -> m1 b1 -> m1 b1
      at <interactive>:1:21-100
      `t1' is a rigid type variable bound by
           the inferred type of
           myFilterM :: MonadPlus m => t -> t1 -> (b -> Bool) -> m b -> m b
           at <interactive>:1:5
    In a stmt of a 'do' expression: x <- m
    In the expression:
        do { x <- m;
             guard (f x);
             return x } ::
          MonadPlus m => (b -> Bool) -> m b -> m b
    In an equation for `myFilterM':
        myFilterM f m
          = do { x <- m;
                 guard (f x);
                 return x } ::
              MonadPlus m => (b -> Bool) -> m b -> m b

<interactive>:1:40:
    Could not deduce (t ~ ((m1 b1 -> m1 b1) -> Bool))
    from the context (MonadPlus m)
      bound by the inferred type of
               myFilterM :: MonadPlus m => t -> t1 -> (b -> Bool) -> m b -> m b
      at <interactive>:1:5-100
    or from (MonadPlus m1)
      bound by an expression type signature:
                 MonadPlus m1 => (b1 -> Bool) -> m1 b1 -> m1 b1
      at <interactive>:1:21-100
      `t' is a rigid type variable bound by
          the inferred type of
          myFilterM :: MonadPlus m => t -> t1 -> (b -> Bool) -> m b -> m b
          at <interactive>:1:5
    The function `f' is applied to one argument,
    but its type `t' has none
    In the first argument of `guard', namely `(f x)'
    In a stmt of a 'do' expression: guard (f x)
Prelude Control.Monad>

Я думаю, проблема в том,что :: не доходит до аргумента.Этот небольшой вариант (обратите внимание на отдельное объявление типа)

let myFilterM f m = do {x <- m; guard (f x); return x}; myFilterM :: (MonadPlus m) => (b -> Bool) -> m b -> m b

работает без проблем.Это может быть связано с новой проверкой типов в GHC 7.