是否可以在 Haskell 中编码通用 "lift" 函数？

Question

我不是 varargs 的忠实粉丝，但我一直认为 applicative (f <$> x <*> y) 和 idiom ([i| f x y |]) 样式都有太多符号。我通常更喜欢 liftA2 f x y 方式，但我也认为 A2 有点难看。从 this question，我了解到可以在 Haskell 中实现可变参数函数。这样，是否可以使用相同的原理来实现提升功能，例如：

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)

但我无法正确设置类型...

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

如您所料，"recursive case" 实例将简单地应用 <*> 一次，然后递归：

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 实例 selection 规则，如果可能，递归情况将始终 selected。

那么你要的函数就是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 中的可变参数函数一样，通常 select 实例的唯一方法是给出显式类型签名。

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 已被弃用，编译器将发出警告。它可能会在某些更高版本中被删除。这可以通过从 {-# LANGUAGE .. #-} pragma 中删除 OverlappingInstances 并将第二个实例更改为

来解决

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"

Second，如果我们改为使用 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首先检查是否有匹配的实例头，匹配成功后才尝试解析约束。我们想把最小的负担放在实例头上，让约束求解器来解决（因为它更灵活，可以延迟做出判断并且可以使用程序其他部分的约束）。

是否可以在 Haskell 中编码通用 "lift" 函数？

Is it possible to encode a generic "lift" function in Haskell?

haskell

typeclass

applicative