Странность логического вывода Хаскелла - PullRequest
Новая
       25

Странность логического вывода Хаскелла

6 голосов
/ 31 июля 2011

Посмотрите на этот вывод из ghci: 

Prelude> :t Data.Map.lookup
Data.Map.lookup :: Ord k => k -> Data.Map.Map k a -> Maybe a
Prelude> :t flip Data.Map.lookup
flip Data.Map.lookup :: Ord a => Data.Map.Map a a1 -> a -> Maybe a1
Prelude> let look = flip Data.Map.lookup
Loading package array-0.3.0.2 ... linking ... done.
Loading package containers-0.4.0.0 ... linking ... done.
Prelude> :t look
look :: Data.Map.Map () a -> () -> Maybe a

Почему предполагаемый тип look отличается от типа flip Data.Map.lookup?

Чтобы дать вам некоторый контекст. Сначала у меня была небольшая программа, и я пытался выяснить, почему она выдает ошибку компилятора: 

import qualified Data.Map as M

type A = String
type B = String
data C = C1 | C2 | C3
     deriving (Eq, Ord)
type D = String

z :: A -> M.Map A B -> M.Map B C -> M.Map C D -> Maybe D
z a aToB bToC cToD = look aToB a >>= look bToC >>= look cToD
  where look = flip M.lookup

Реакция Гхи: 

Prelude> :load main.hs
[1 of 1] Compiling Main             ( main.hs, interpreted )
Failed, modules loaded: none.

main.hs:10:52:
    Couldn't match expected type `C' with actual type `[Char]'
    Expected type: C -> Maybe D
      Actual type: A -> Maybe a0
    In the return type of a call of `look'
    In the second argument of `(>>=)', namely `look cToD'

Я обнаружил, что этот вариант хорошо компилируется (определения типов совпадают): 

x :: A -> M.Map A B -> M.Map B C -> Maybe C
x a aToB bToC = look aToB a >>= look bToC
  where look = flip M.lookup

y :: A -> M.Map A B -> M.Map B C -> M.Map C D -> Maybe D
y a aToB bToC cToD = (x a aToB bToC) >>= look cToD
  where look = flip M.lookup

И после некоторого эксперимента выяснилось, что если я явно укажу тип look - первая версия тоже хорошо скомпилируется: 

z :: A -> M.Map A B -> M.Map B C -> M.Map C D -> Maybe D
z a aToB bToC cToD = look aToB a >>= look bToC >>= look cToD
  where look :: (Ord a) => M.Map a b -> a -> Maybe b
        look = flip M.lookup

Что приводит меня к моему первому вопросу.

1 Ответ

7 голосов
/ 31 июля 2011

По умолчанию привязки верхнего уровня являются неполиморфными, если не указан явный спецификатор типа; это известно как « ограничение мономорфизма ». Поскольку не был указан спецификатор типа, GHC пришлось выбирать способ создания экземпляра k во время определения функции. Случилось выбрать k = ().

Идея, лежащая в основе этого, заключается в том, что полиморфизм может снизить производительность, вводя множество вызовов vtable в окончательный скомпилированный код; принудительно разрешая их во время компиляции, если явно не указано иное, этих издержек можно избежать. Это решение является весьма спорным. GHC поддерживает расширение для полного отключения ограничения мономорфизма, передавая -XNoMonomorphismRestriction.

...