Можно ли кодировать общую функцию "подъема" в Haskell?

Я не самый большой поклонник varargs, но я всегда считал, что стили аппликативного (f <$> x <*> y) и идиомы ([i| f x y |]) слишком много символов. Обычно я предпочитаю идти liftA2 f x y, но я тоже думаю, что A2 немного уродлив. Из этого вопроса, я узнал, что в Haskell можно реализовать функции vararg. Таким образом, можно ли использовать тот же принцип для реализации функции подъема, что:

lift f a b == pure f <*> a <*> b

Я попытался заменить + на <*> на цитируемый код:

class Lift r where 
    lift :: a -> r

instance Lift a where
    lift = id

instance (Lift r) => Lift (a -> r) where
    lift x y = lift (x <*> y)

Но мне не удалось получить правильные типы...

Ответы

Ответ 1

Обратите внимание, что вы можете связать любое число <*>, чтобы получить функцию формы

f (a0 -> .. -> an) -> (f a0 -> .. -> f an)

Если у нас есть тип a0 -> .. -> an и f a0 -> .. -> f an, мы можем вычислить f из этого. Мы можем кодировать это отношение и наиболее общий тип, как следует

class Lift a f b | a b -> f where 
  lift' :: f a -> b

Как вы и ожидаете, экземпляр "рекурсивный случай" просто применит <*> один раз, а затем рекурсирует:

instance (a ~ a', f' ~ f, Lift as f rs, Applicative f) 
      => Lift (a -> as) f (f' a' -> rs) where  
  lift' f a = lift' $ f <*> a

Основной случай - когда функции больше нет. Поскольку вы не можете утверждать, что "a не является типом функции", это зависит от совпадающих экземпляров:

instance (f a ~ b) => Lift a f b where 
  lift' = id

Из-за правил выбора экземпляров GHCs рекурсивный случай всегда выбирается, если это возможно.

Тогда вам нужна функция lift' . pure:

lift :: (Lift a f b, Applicative f) => a -> b
lift x = lift' (pure x)

Здесь важна функциональная зависимость от Lift. Так как f упоминается только в контексте, эта функция будет плохо напечатана, если мы не сможем определить, что f знает только a и b (которые появляются в правой части =>),

Для этого требуется несколько расширений:

{-# LANGUAGE 
    OverlappingInstances
  , MultiParamTypeClasses
  , UndecidableInstances
  , FunctionalDependencies
  , ScopedTypeVariables
  , TypeFamilies
  , FlexibleInstances
  #-}

и, как обычно, с вариационными функциями в Haskell, обычно единственный способ выбрать экземпляр - дать явную подпись типа.

lift (\x y z -> x * y + z) readLn readLn readLn :: IO Int

Как я его написал, GHC с радостью примет Lift, который является полиморфным в аргументах f (но не f).

lift (+) [1..5] [3..5] :: (Enum a, Num a) => [a]

Иногда контекст достаточно, чтобы вывести правильный тип. Обратите внимание, что тип аргумента снова является полиморфным.

main = lift (\x y z -> x * y + z) readLn readLn readLn >>= print

Как по GHC >= 7.10, OverlappingInstances устарел, и компилятор выдаст предупреждение. Вероятно, он будет удален в более поздней версии. Это можно устранить, удалив OverlappingInstances из прагмы {-# LANGUAGE .. #-} и изменив второй экземпляр на

instance {-# OVERLAPS #-} (f a ~ b) => Lift a f b where

Ответ 2

Я предполагаю, что вы предпочитаете использовать lift без аннотаций типа. В этом случае есть в основном два варианта:

Сначала, если мы используем OverlappingInstances, полиморфным функциям нужны аннотации:

{-# LANGUAGE
  OverlappingInstances,
  MultiParamTypeClasses,
  UndecidableInstances,
  FunctionalDependencies,
  FlexibleInstances,
  TypeFamilies
  #-}

import Control.Applicative

class Applicative f => ApN f a b | a b -> f where
  apN :: f a -> b

instance (Applicative f, b ~ f a) => ApN f a b where
  apN = id

instance (Applicative f, ApN f a' b', b ~ (f a -> b')) => ApN f (a -> a') b where
  apN f fa = apN (f <*> fa)

lift :: ApN f a b => a -> b
lift a = apN (pure a)

-- Now we can't write "lift (+) (Just 0) Nothing"
-- We must annotate as follows: 
--   lift ((+) :: Int -> Int -> Int) (Just 0) Nothing
-- Monomorphic functions work fine though:
--   lift (||) (Just True) (Just True) --> results in "Just True"

Второй, если вместо этого использовать IncoherentInstances, lift будет работать без аннотаций даже по полиморфным функциям. Однако некоторые сложные вещи все равно не будут проверяться, например (lift . lift) (+) (Just (Just 0)) Nothing.

{-# LANGUAGE 
  IncoherentInstances, MultiParamTypeClasses,
  UndecidableInstances,ScopedTypeVariables,
  AllowAmbiguousTypes, FlexibleInstances, TypeFamilies
  #-}

import Control.Applicative

class Applicative f => ApN f a b where
  apN :: f a -> b

instance (Applicative f, b ~ f a) => ApN f a b where
  apN = id

instance (Applicative f, ApN f a' b', b ~ (f a -> b')) => ApN f (a -> a') b where
  apN f fa = apN (f <*> fa)

lift :: forall f a b. ApN f a b => a -> b
lift a = (apN :: f a -> b) (pure a)

-- now "lift (+) (Just 0) (Just 10)" works out of the box

Я представил два решения вместо одного с IncoherentInstances, потому что IncoherentInstances является довольно грубым расширением, которого следует избегать, если это возможно. Вполне возможно, что здесь хорошо, но я счел целесообразным предоставить альтернативное решение. В любом случае.

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

instance (Applicative f) => ApN f a (f a) where
  apN = id

Я пишу

instance (Applicative f, b ~ f a) => ApN f a b where
  apN = id

Кроме того, в другом случае я использую простой параметр b в голове экземпляра и добавляю b ~ (f a ~ b') к ограничениям.

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