Haskell - 形式 A -> A -> ... -> A 的所有函数

Question

我有一个类型(称之为 A)，我想创建一个 A -> A、A -> A -> A、A -> A -> A -> ... 等类型的函数的类型类.这不起作用:

{-# LANGUAGE FlexibleInstances #-}

data A = A

class AsToA a where
  takeA :: AsToA b => a -> A -> Either A b

instance AsToA (A -> A) where
  takeA f a = Left (f a)

instance AsToA b => AsToA (A -> b) where
  takeA f a = Right (f a)

我收到以下错误消息:

AsToA.hs:12:22:
    Couldn't match expected type ‘b1’ with actual type ‘b’
      ‘b’ is a rigid type variable bound by
          the instance declaration at AsToA.hs:11:10
      ‘b1’ is a rigid type variable bound by
          the type signature for

             takeA :: AsToA b1 => (A -> b) -> A -> Either A b1
          at AsToA.hs:12:3
    Relevant bindings include
      f :: A -> b (bound at AsToA.hs:12:9)
      takeA :: (A -> b) -> A -> Either A b1 (bound at AsToA.hs:12:3)
    In the first argument of ‘Right’, namely ‘(f a)’
    In the expression: Right (f a)

有什么想法吗？非常感谢您的建议。

Answer 1

两者之间存在一些混淆b s:

class AsToA a where
  takeA :: AsToA b => a -> A -> Either A b

instance AsToA b => AsToA (A -> b) where
  takeA f a = Right (f a)

这些不一样。让我们将第一个重命名为 c

class AsToA a where
  takeA :: AsToA c => a -> A -> Either A c

instance AsToA b => AsToA (A -> b) where
  takeA f a = Right (f a)

现在，Right (f a)类型为Either A b但应该有类型 Either A c对于任何 c这样AsToA c成立。这不会进行类型检查。

这里的问题是签名

  takeA :: AsToA c => a -> A -> Either A c

promise takeA可返回Either A c对于任何 c ，调用者的选择。我猜这不是你想要的。

<小时/>

我仍然不确定实际的预期结果是什么，但我猜问题类似于以下问题。

Given a function f of type A->A->...->A return a function \x -> f x x ..., with one application of x for each -> in the type (hence of type A->A).

一个可能的解决方案是

{-# LANGUAGE FlexibleInstances, OverlappingInstances #-}
data A = A -- could be anything

class C f where
   takeA :: f -> A -> A

instance C (A -> A) where
   takeA f = f

instance C b => C (A -> b) where
    takeA f = \x -> takeA (f x) x

请注意，这需要 OverlappingInstances被使用，这是相当邪恶的。我建议避免它。

为了避免这种情况，在这种情况下，即使是为类型A .

{-# LANGUAGE FlexibleInstances #-}
data A = A -- could be anything

class C f where
   takeA :: f -> A -> A

instance C A where
   takeA a = \_ -> a

instance C b => C (A -> b) where
    takeA f = \x -> takeA (f x) x