Haskell непонимание состава fmap

Question

Если я составлю два fmap s

Prelude> :t (fmap.fmap)
(fmap.fmap)
  :: (Functor f, Functor f1) => (a -> b) -> f1 (f a) -> f1 (f b)

, я получу функцию, которая применяет функцию к значению внутри двух вложенных уровней структуры, f1 и f.

И я могу его использовать - это работает, как я ожидал:

Prelude> (fmap.fmap) (+1) [[1,2]]
[[2,3]]

С предполагаемым типом, как я ожидал (2 уровня структуры вокруг результата)

Prelude> :t  (fmap.fmap) (+1) [[1,2]]
(fmap.fmap) (+1) [[1,2]] :: Num b => [[b]]

Следующее не работает работай. Я тоже ожидаю этого (потому что мы не можем применить sum к одному числу):

Prelude>  (fmap.fmap) sum [[1,2]]

<interactive>:39:2: error:
    • Could not deduce (Num (t0 b))
      from the context: (Num (t b), Num b, Foldable t)
        bound by the inferred type for ‘it’:
                   (Num (t b), Num b, Foldable t) => [[b]]
        at <interactive>:39:2-24
      The type variable ‘t0’ is ambiguous
    • In the ambiguity check for the inferred type for ‘it’
      To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
      When checking the inferred type
        it :: forall (t :: * -> *) b.
              (Num (t b), Num b, Foldable t) =>
              [[b]]
Prelude> :t  (fmap.fmap) sum [[1,2]]
(fmap.fmap) sum [[1,2]] :: (Num (t b), Num b, Foldable t) => [[b]]

НО! Если я изменю один уровень структуры на тип Maybe:

Prelude> (fmap.fmap) sum Just [1,2]
Just 3

, тогда он начнет работать, но, на мой взгляд, нарушит сигнатуру типа (fmap.fmap) :: (Functor f, Functor f1) => (a -> b) -> f1 (f a) -> f1 (f b) (потому что он применяет функцию sum внутри Это первый уровень структуры, а не второй, как я ожидал). значения списка (по сравнению с числами в первых примерах):

Prelude> (fmap.fmap) sum (Just [[1,2],[2,3]])
Just [3,5]

Но что происходит здесь:

Prelude> (fmap.fmap) sum Just [1,2]
Just 3

1. Почему пропускается первый уровень структуры?

2. Какой здесь порядок применения функций?

3. Как Haskell определяет окончательный тип?

    Prelude> :t (fmap.fmap) sum Just [1,2]
    (fmap.fmap) sum Just [1,2] :: Num t => Maybe t
   

Почему Maybe t, а не Maybe List t как я понимаю (fmap.fmap) должен определять f1 (f b) два уровня структуры, а не один?

Answer 1

Давайте посчитаем, представив, что числовые c литералы - это Int s для простоты.

(fmap.fmap) sum Just [1,2]
= fmap (fmap sum) Just [1,2]
        |         |    \ -- an additional argument applied to the result of fmap
        |         \ -- the value with a type of the form f a with f Functor
        \ -- the function to fmap

Здесь Just - это функция [Int] -> Maybe [Int], поэтому первая fmap работает с функтором f = (->) [Int], у нас есть fmap = (.), потому что именно так он определен в Functor ((->) [Int]).

= (.) (fmap sum) Just [1,2]
= (fmap sum) (Just [1,2])

Теперь fmap f (Just x) = Just (f x), поскольку именно так определяется Functor Maybe.

= Just (sum [1,2])
= Just 3

1. почему первый уровень структуры пропущен?

Это не так. Первый уровень (->) [Int].

какой здесь порядок применения функций?

Обычный. fmap.fmap применяется к sum. Результат применяется к Just. Окончательный результат применяется к [1,2].

как Haskell выводит окончательный тип?

Он видит, что Just - это «значение, заключенное внутри функтора (->) [Int]», и использует это для создания экземпляра первый fmap. Второй fmap вместо этого используется на уровне Maybe, поскольку Just возвращает его.

Answer 2

Вы только что обнаружили, что функции сами являются функторами . Это утверждение может показаться немного запутанным, поэтому давайте рассмотрим его немного дальше. Давайте посмотрим на оператор композиции функции (.):

Prelude> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

Но теперь давайте немного перепишем сигнатуру типа:

(.) :: (b -> c) -> ((->) a b) -> ((->) a c)

Здесь я вёл себя так, как будто функция Стрелка композиции была обычным инфиксным оператором и могла быть помещена перед тем, что выглядело как его «параметры типа» (что на самом деле может быть). И теперь мы замечаем кое-что интересное - (.) выглядит почти так же, как fmap! См .:

(.)  ::              (b -> c) -> ((->) a b) -> ((->) a c)
fmap :: Functor f => (b -> c) ->  f      b  ->  f      c

И на самом деле можно написать экземпляр Functor для частично примененной стрелки функции (->) r (где ((->) r) a совпадает с (r -> a)):

instance Functor ((->) r) where
    fmap = (.)
-- type signature here would be:
--  fmap :: (a -> b) -> ((->) r) a -> ((->) r) b
-- that is:
--  fmap :: (a -> b) -> (r -> a) -> (r -> b)

Итак, если f и g - функции, то fmap f g = f . g.

Как это соотносится с вашим вопросом? Давайте посмотрим на выражение, в котором вы запутались:

Prelude> (fmap.fmap) sum Just [1,2]
Just 3

Давайте go рассмотрим это по крупицам. Во-первых, обратите внимание, что это можно переписать как: (fmap (fmap sum) Just) [1,2]. Теперь fmap sum - это функция, то есть функтор! Итак, используя fmap = (.) для функций, как я сказал выше, это становится: ((fmap sum) . Just) [1,2], то есть fmap sum (Just [1,2]). И, конечно же, это просто означает Just 3.

Answer 3

Спасибо за ответы, он убирает для меня, что Just not Just [1,2] идет в качестве второго аргумента в (fmap.fmap).

I хотите написать вывод типа, как я понимаю более подробно (поправьте меня, если я ошибаюсь)

У нас есть выражение: (fmap.fmap) sum Just [1,2]

тип ( fmap.fmap) is (a -> b) -> f1 (fa) -> f1 (fb)

это определяет, что он принимает два следующих аргумента - sum и Просто и функция возврата.

сумма имеет тип List int -> int (для простоты int) это означает, что a = List int и b = int

Второй аргумент Просто имеет тип a -> Может быть a или другие слова (->) a (Может быть) так f1 = (->) a и f = Может

это означает, что f1 (fb) = (->) (List int) (Возможно int)

Или другими словами тип результата выражения (fmap.fmap) sum Just is * 10 49 * List int -> Maybe int Итак, результатом является функция.

И, наконец, мы применяем значение [1,2] к этой функции и получаем значение Just 3, как и ожидалось с введенными типами.