Каким будет экземпляр Functor для следующего типа: newtype F2 xa = F2 ((a -> x) -> a) - PullRequest
Новая
       18

Каким будет экземпляр Functor для следующего типа: newtype F2 xa = F2 ((a -> x) -> a)

0 голосов
/ 18 апреля 2020

Итак, я хочу написать функцию fmap для вышеупомянутого типа, но я застрял здесь: 

instance Functor (F2 x) where
 fmap :: (a -> b) -> (F2 x a) -> (F2 x b)
 fmap f (F2 g) = F2 ( f _ )

Ответы [ 2 ]

8 голосов
/ 18 апреля 2020

Хорошая стратегия здесь - следовать типам. GH C может помочь нам в этом, если мы напишем неполные определения с напечатанными дырами : 

newtype F2 x a = F2 ((a -> x) -> a)

instance Functor (F2 x) where
    fmap f (F2 g) = _

Если мы попытаемся скомпилировать это, GH C сообщит: 

Diatonic.hs:275:21: error:
    • Found hole: _ :: F2 x b
      Where: ‘b’ is a rigid type variable bound by
               the type signature for:
                 fmap :: forall a b. (a -> b) -> F2 x a -> F2 x b
               at Diatonic.hs:275:5-8
             ‘x’ is a rigid type variable bound by
               the instance declaration
               at Diatonic.hs:274:10-23
    • In the expression: _
      In an equation for ‘fmap’: fmap f (F2 g) = _
      In the instance declaration for ‘Functor (F2 x)’
    • Relevant bindings include
        g :: (a -> x) -> a (bound at Diatonic.hs:275:16)
        f :: a -> b (bound at Diatonic.hs:275:10)
        fmap :: (a -> b) -> F2 x a -> F2 x b (bound at Diatonic.hs:275:5)
    |
275 |     fmap f (F2 g) = _
    |

Это означает, что мы должны заполнить отверстие значением F2 x b. Единственный способ создать его - использовать конструктор (для следующих шагов я опущу неизменный шаблон): 

fmap f (F2 g) = F2 _

• Found hole: _ :: (b -> x) -> b

Итак, нам нужна функция, которая принимает b -> x , Мы можем создать один. Давайте назовем его аргумент k и посмотрим, сможем ли мы завершить его тело: 

fmap f (F2 g) = F2 (\k -> _)

• Found hole: _ :: b

Единственное, что может создать b, это f :: a -> b: 

fmap f (F2 g) = F2 (\k -> f _)

• Found hole: _ :: a

Единственное, что может создать a, это g :: (a -> x) -> a: 

fmap f (F2 g) = F2 (\k -> f (g _))

• Found hole: _ :: a -> x

Мы должны предоставить функцию a -> x, поэтому давайте добавим еще одну лямбду (возможный ярлык см. в заключительной части ответа): 

fmap f (F2 g) = F2 (\k -> f (g (\a -> _)))

• Found hole: _ :: x

Единственное, что может произвести x, это k :: b -> x

fmap f (F2 g) = F2 (\k -> f (g (\a -> k _)))

• Found hole: _ :: b

Единственное, что может создать b, это f :: a -> b: 

fmap f (F2 g) = F2 (\k -> f (g (\a -> k (f _))))

• Found hole: _ :: a

Если мы попытаемся использовать g для создания значения a, как мы делали несколько шаги go, мы попадем в ловушку замкнутого круга. Однако нам не нужно делать это на этот раз, так как аргумент a лямбды находится в области видимости: 

fmap f (F2 g) = F2 (\k -> f (g (\a -> k (f a))))

И мы закончили.

(Это стоит упоминая, что ваш F2 предоставляется преобразователями , , где он известен как Select.)

Определение, возможно, выглядит немного опрятнее, если мы напишем \a -> k (f a) pointfree: 

instance Functor (F2 x) where
    fmap f (F2 g) = F2 (\k -> f (g (k . f)))

Возможно, мы пропустили прямо из отверстия a -> x сюда, заметив, что наш единственный жизнеспособный вариант - составление f :: a -> b и k :: b -> x.

2 голосов
/ 18 апреля 2020

Вы можете заставить GH C выполнять за вас тяжелую работу: 

GHCi, version 8.8.2: https://www.haskell.org/ghc/  :? for help
Prelude> :set -ddump-deriv -dsuppress-all -XDeriveFunctor
Prelude> newtype F2 x a = F2 ((a -> x) -> a) deriving(Functor)

==================== Derived instances ====================
Derived class instances:
  instance Functor (F2 x) where
    fmap f_a1bk (F2 a1_a1bl)
      = F2
          ((\ b4_a1bm b5_a1bn
              -> f_a1bk
                   (b4_a1bm
                      ((\ b2_a1bo b3_a1bp
                          -> (\ b1_a1bq -> b1_a1bq) (b2_a1bo (f_a1bk b3_a1bp)))
                         b5_a1bn)))
             a1_a1bl)
    (<$) z_a1br (F2 a1_a1bs)
      = F2
          ((\ b6_a1bt b7_a1bu
              -> (\ b5_a1bv -> z_a1br)
                   (b6_a1bt
                      ((\ b3_a1bw b4_a1bx
                          -> (\ b2_a1by -> b2_a1by)
                               (b3_a1bw ((\ b1_a1bz -> z_a1br) b4_a1bx)))
                         b7_a1bu)))
             a1_a1bs)


Derived type family instances:


Prelude>

Переименовать странные имена GH C и удалить излишние отступы, и в итоге вы получите: 

instance Functor (F2 x) where
  fmap f (F2 a1) = F2 ((\b4 b5 -> f (b4 ((\b2 b3 -> (\b1 -> b1) (b2 (f b3))) b5))) a1)

Теперь мы можем сделать несколько упрощений, чтобы сделать это более понятным. Давайте посмотрим на это подвыражение: 

(\b2 b3 -> (\b1 -> b1) (b2 (f b3))) b5

(\b1 -> b1) - это функция тождества, от которой мы можем бета-уменьшить, чтобы избавиться от нее: 

(\b2 b3 -> b2 (f b3)) b5

Теперь мы можем снова бета-уменьшить на этот раз b5 для b2: 

\b3 -> b5 (f b3)

Теперь это явно эквивалентно b5 . f. Подключите его обратно: 

instance Functor (F2 x) where
  fmap f (F2 a1) = F2 ((\b4 b5 -> f (b4 (b5 . f))) a1)

Еще одно бета-сокращение: a1 для b4: 

instance Functor (F2 x) where
  fmap f (F2 a1) = F2 (\b5 -> f (a1 (b5 . f)))

И все готово! Никакой тяжелой работы с нашей стороны не требуется.

...