是否可以在Haskell中编码通用的"提升"功能？

Question

我不是varargs的最大粉丝,但我一直认为applicative(f <$> x <*> y)和idiom([i| f x y |])样式都有太多的符号.我通常喜欢liftA2 f x y这样做,但我也认为A2有点难看.从这个问题,我已经了解到可以在Haskell中实现vararg函数.这样,是否可以使用相同的原理来实现提升功能,例如:

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

我试过替换引用代码的+by <*>:

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)

但我无法让这些类型正确......

Answer 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 

由于GHC实例选择规则,如果可能,将始终选择递归情况.

然后你想要的功能是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 .. #-}pragma中删除并将第二个实例更改为来解决

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

Answer 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在实例头中使用了一个plain 参数并添加b ~ (f a ~ b')到约束中.

这样做的原因是GHC首先检查是否存在匹配的实例头,并且只有在成功匹配后才尝试解析约束.我们希望在实例头上放置最少的负担,并让约束求解器对事物进行排序(因为它更灵活,可以延迟判断并可以使用程序其他部分的约束).