是否有可能编码通用的“升降机”函数在Haskell中？ [英] Is it possible to encode a generic "lift" function in Haskell?

问题描述

我并不是可变参与者的最大粉丝，但我一直认为应用（ f <$> x> y> ）和成语（ [i | fxy |] ）样式具有太多符号。我通常更喜欢使用 liftA2 f x y 方式，但我也认为A2有点难看。从这个问题，我知道可以实现可变参数函数在Haskell中。这样，是否可以使用相同的原则来实现升降功能，例如：

  lift fab == pure f * a * b 
  

我尝试将 + 由< *> 引用代码：

  class Lift r其中
 lift :: a  - > r 
 
 instance lift a where 
 lift = id 
 
 instance（Lift r）=> Lift（a  - > r）其中
 lift xy = lift（x * y）
  

但是我无法设法获得正确的类型...

解决方案

请注意，您可以链接任何< $> ，以获得表格的功能

 <$ c $ （a 0  - >  - > an） - > （f a0  - > ..> f an）
  

如果我们有 a0 - > ... - >一个和 f a0 - > ... - > f an ，我们可以从中计算 f 。我们可以编码这个关系，最常用的类型，如下所示：

  class提升一个f b | a b  - > f其中
 lift':: f a  - > b 
  

正如您所预料的那样，递归大小写实例将简单地应用 < / code>一次然后递归：



  instance（a〜a'，f' 〜f，提升为f rs，应用f）
 => （a  - > as）f（f'a' - > rs）其中
 lift'f a = lift'$ f * a 
  

基本情况是没有更多功能的情况。由于你实际上不能断言 a 不是函数类型，所以它依赖于重叠的实例：



  instance（fa〜b）=>提升afb其中
 lift'= id 
  

由于GHCs实例选择规则，递归实例将尽可能选择。



然后你想要的功能是 lift'。纯粹：

  lift ::（Lift a f b，Applicative f）=> a  - > b 
 lift x = lift'（pure x）
  

这是函数依赖关系电梯变得非常重要。由于 f 仅在上下文中提及，因此除非我们能够确定 f 知道什么只有 a 和 b （确实出现在 =>> ）。

这需要几个扩展名：

  { - ＃LANGUAGE 
 OverlappingInstances 
，MultiParamTypeClasses 
，UndecidableInstances 
，FunctionalDependencies 
，ScopedTypeVariables 
，TypeFamilies 
，FlexibleInstances 
＃ - } 
  

和通常的Haskell中的可变参数函数一样，通常选择一个实例的唯一方法是给出一个明确的类型签名。

  lift（\xyz  - > x * y + z）readLn readLn readLn :: IO Int 
  

GHC会很乐意接受 lift 这在 f （但不是 f 本身）的参数中是多态的。

  lift（+）[1..5] [3..5] ::（Enum a，Num a）=> [a] 
  

有时，上下文足以推断出正确的类型。注意参数类型又是多态的。

  main = lift（\xyz  - > x * y + z）readLn readLn readLn> => print 
  





---

GHC> = 7.10， OverlappingInstances 已被弃用，编译器将发出警告。它可能会在稍后的版本中被删除。这可以通过从 { - ＃LANGUAGE ..＃ - } pragma中删除 OverlappingInstances 并修改第二个实例到

 实例{ - ＃OVERLAPS＃ - }（fa〜b）=>举一个f b，其中
  

I'm not the biggest fan of varargs, but I always thought both the applicative (f <$> x <*> y) and idiom ([i| f x y |]) styles have too many symbols. I usually prefer going the liftA2 f x y way, but I, too, think that A2 is a little ugly. From this question, I've learned it is possible to implement vararg functions in Haskell. This way, is it possible to use the same principle in order implement a lift function, such that:

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

I've tried replacing the + by <*> on the quoted code:

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)

But I couldn't manage to get the types right...

解决方案

Notice that you can chain any number of <*>, to get a function of the form

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

If we have the type a0 -> .. -> an and f a0 -> .. -> f an, we can compute f from this. We can encode this relation, and the most general type, as follows

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

As you may expect, the "recursive case" instance will simply apply <*> once, then recurse:

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

The base case is when there is no more function. Since you can't actually assert "a is not a function type", this relies on overlapping instances:

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

Because of GHCs instance selection rules, the recursive case will always be selected, if possible.

Then the function you want is lift' . pure :

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

This is where the functional dependency on Lift becomes very important. Since f is mentioned only in the context, this function would be ill-typed unless we can determine what f is knowing only a and b (which do appear in the right hand side of =>).

This requires several extensions:

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

and, as usual with variadic functions in Haskell, normally the only way to select an instance is to give an explicit type signature.

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

The way I have written it, GHC will happily accept lift which is polymorphic in the arguments to f (but not f itself).

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

Sometimes the context is sufficient to infer the correct type. Note that the argument type is again polymorphic.

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

---

As of GHC >= 7.10, OverlappingInstances has been deprecated and the compiler will issue a warning. It will likely be removed in some later version. This can be fixed by removing OverlappingInstances from the {-# LANGUAGE .. #-} pragma and changing the 2nd instance to

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

这篇关于是否有可能编码通用的“升降机”函数在Haskell中？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！