Функторы и Применения для типов вида (* → *) → *

Я столкнулся с ситуацией, когда мой код выиграл бы от использования абстракций Functor и Applicative -like, но для типов типов (* -> *) -> *. Определение более высокоподобного функтора можно сделать с помощью RankNTypes, как этот

class HFunctor f where
    hfmap :: (forall x. a x -> b x) -> f a -> f b

Но более высокая версия Applicative немного сложнее. Это лучшее, что я мог придумать:

class HFunctor f => HApplicative f where
    hpure  :: (forall x. a x) -> f a
    (<**>) :: f (a :-> b) -> f a -> f b

newtype (:->) a b x = HFunc (a x -> b x)

infixr 5 :->

Нам нужен тип обертки :-> для того, чтобы иметь функции с видом * -> *, но это не позволяет нам хорошо использовать функциональное приложение, как мы можем, с <$> и <*> для обычных приложений. Я могу справиться с помощником, например

liftHA2 :: HApplicative f => (forall x. a x -> b x -> c x) -> f a -> f b -> f c
liftHA2 f fa fb = hpure (fun2 f) <**> fa <**> fb where
    fun2 = HFunc . (HFunc .)

Но было бы неплохо иметь общий способ "поднять" функции любой арности.

Некоторые простые примеры того, как можно использовать вышеуказанные примеры:

data Example f = Example (f Int) (f String)

instance HFunctor Example where
    hfmap f (Example i s) = Example (f i) (f s)

instance HApplicative Example where
    hpure a = Example a a
    Example (HFunc fi) (HFunc fs) <**> Example i s = Example (fi i) (fs s)

e :: Example []
e = Example [1,2,3] ["foo", "bar"]

e' :: Example ((,) Int)
e' = hfmap (length &&& head) e  -- Example (3,1) (2, "foo")

e'' :: Example []
e'' = liftHA2 (++) e e  -- Example [1,2,3,1,2,3] ["foo", "bar", "foo", "bar"]

Итак, мой вопрос: каковы названные выше классы имен и они уже предоставлены какой-либо библиотекой в хаке? По googling я придумал Functor2 в linear-maps и HFunctor в multi-rec, но ни то, что мне нужно.

Кроме того, существует ли способ написать HApplicative без обертки :-> или каким-либо другим способом упростить работу с функциями?

Ответ 1

HFunctor, о котором я обычно думаю, (* -> *) -> * -> * - то есть законный функтор на функторах. Это имеет разные характеристики, чем тот, о котором вы думаете.

Здесь, как определить его, а также "моноидальную" версию аппликативного на нем.

type Nat f g = forall a. f a -> g a

class HFunctor (f :: (* -> *) -> * -> *) where
    hfmap :: (Nat g h) -> Nat (f g) (f h)

data Prod f g a = Prod (f a) (g a)

class HFunctor f => HApplicative f where
    hpure  :: Nat g (f g)
    htensor :: Nat (Prod (f g) (f h)) (f (Prod g h))

Я попытаюсь позже обновить некоторые идеи о том, что это такое и как его использовать.

Это не совсем то, о чем вы просите, я понимаю, но я был вдохновлен попробовать его на вашем посту.

Меня тоже интересовал бы ваш конкретный вариант использования.

К вашим двум конкретным вопросам: A) HFunctor, о котором вы описываете, был описан ранее в разных случаях, я думаю, в частности, Гиббонсом, но я не знаю, как это упаковано. Я, конечно, раньше не видел Аппликацию. B) Я думаю, вы застряли с оберткой, потому что мы не можем частично применять синонимы типов.