Частично примененный тип функции (a ->) как экземпляр Functor в Haskell - PullRequest
Новая
       2

Частично примененный тип функции (a ->) как экземпляр Functor в Haskell

3 голосов
/ 21 февраля 2020

Я просматриваю книгу «Программирование в Haskell» (второе издание) и просто наткнулся на упражнение 2, глава 12, часть 2: 

instance Functor ((->) a) where
  fmap = TODO

, где ответ: 

instance Functor ((->) a) where
  fmap = (.)

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

Я придумал эти два: 

main = do
    putStrLn . show $ (fmap (+1) (*2)) (5 :: Int)
    putStrLn . show $ (fmap (show) (+1)) 3

Правильно ли иллюстрируют мои примеры мои примеры?

fmap, учитывая два аргумента:

  • частично применен функция (функция)
  • другая частично примененная функция (функтор)

ОБНОВЛЕНИЕ

fmap с двумя аргументами :

  • функция (функция)
  • другая функция (функтор)

просто выглядит странно для меня, и я не уверен Я понял концепцию правильно.

Я вижу некоторые похожие вопросы по SO (например, this ), где this - почти то, что я ищу, но не совсем (я просто ищу примеры функторов и ничего больше - без аппликативов и без монад). * 1 046 *

1 Ответ

6 голосов
/ 21 февраля 2020

Нет ничего более того, что для функтора f реализация fmap (известно, что для любого возможного f существует не более одной реализации) должна иметь тип (a -> b) -> f a -> f b, и удовлетворить два функтора l aws: 

fmap id = id
fmap (g . h) = fmap g . fmap h

Когда f является конструктором типа (->) r - то есть когда f a означает r -> a - тогда необходимая сигнатура типа: 

(a -> b) -> (r -> a) -> (r -> b)

(последняя пара скобок там не нужна, но я оставил их там, потому что это облегчает просмотр "шаблона"), который легко увидеть, является именно сигнатурой (.) оператор.

Что касается двух l aws, то совершенно очевидно, что они должны держаться, когда вы записываете, что они говорят. Я докажу их, выписав все кропотливо: 

fmap id = (.) id
        = \g -> id . g
        = \g -> (\a -> id (g a))
        = \g -> (\a -> g a)
        = \g -> g
        = id

и 

fmap (g . h) = (.) (g . h)
             = \g1 -> (g . h) . g1
             = \g1 -> \a -> ((g . h) . g1) a
             = \g1 -> \a -> g (h (g1 a))

(fmap g) . (fmap h) = ((.) g) . ((.) h)
                    = \g1 -> ((.) g) (h . g1)
                    = \g1 -> g . h . g1
                    = \g1 -> \a -> g (h (g1 a))

, поэтому они также одинаковы.

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

Важно следующее: когда f определен как f a = r -> a, тогда оператор композиции имеет тот же тип, что и fmap, и удовлетворяет обоим функторам l aws - поэтому композиция является юридическим определением ( и только такое определение) fmap для создания Functor экземпляра для f. В этом нет ничего большего, по крайней мере, формально.

...