Haskell“伪函子”

Question

我有一个多项式，

data Poly a = Poly [a]

我希望能够执行类似 fmap (take 3) polynomial 的操作，但我不能，因为 Poly 并不是真正的函子，因为我在 fmap 中使用的 f 只能是 [a] -> 类型[b]，而不是a -> b.。

有什么成语或方式可以表达我想要的吗？

---

编辑：这是一个执行我想要的用法的函数

myMap :: ([a] ->[b]) -> P a -> P b
myMap f (P x) = P (f x)

：

*Main> myMap (take 3) (P [1..])
P [1,2,3]

您可以从类型 sig 中看到它几乎 fmap，但不完全是。我显然有能力为 myMap 编写代码，但我只是想知道是否应该使用另一种习惯用法。

Answer 1

由于您允许将任何函数应用于系数列表，因此您的数据类型实际上仅用于两个目的。

• 您可以获得额外的类型安全性，因为 Poly [a] 与 [a] 不同。
• 您可以定义不同的实例。

如果您不需要其中任何一个，您也可以使用类型别名。

type Poly a = [a]

现在您可以直接在其上应用任何列表功能。

另一方面，如果您想要一个不同的类型，您可能会发现 newtype 包很有用。例如，给出这个例子。

instance Newtype (Poly a) [a] where
  pack = Poly
  unpack (Poly x) = x

您现在可以编写类似的内容，

foo :: Poly a -> Poly a
foo = over Poly (take 3)

尽管如果您的 myMap 足以满足您的目的，那么这可能有点过分了。

---

除此之外，我认为以这种方式公开数据类型的表示首先可能不是一个好主意，因为它会使代码的其余部分密切依赖于这种表示。

这使得以后更难更改为不同的表示形式。例如，您可能想要更改为稀疏表示，例如

data Poly a = Poly [(a, Int)]

Int 是项的幂。我建议考虑一下您想要公开哪些操作，并将自己限制在这些操作范围内。例如，拥有一个基于每个元素工作的 Functor 实例可能是有意义的。

instance Functor Poly where
    fmap f (Poly x) = Poly $ map f x

现在，对稀疏表示的更改使客户端代码保持不变。只有实例（以及依赖于表示的少数其他函数）需要更改。

instance Functor Poly where
    fmap f (Poly x) = Poly $ map (first f) x

Answer 2

这不起作用，但我认为无论如何，它都足够有趣，值得分享：

{-#LANGUAGE GADTs #-}

data Poly a where
   Poly :: [b] -> Poly [b]

我们现在有一个在 a 上参数化的 Poly 类型，但实际上 a 必须是一个列表：

~% ghci Poly.hs
GHCi, version 6.8.2: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( Poly.hs, interpreted )
Ok, modules loaded: Main.
*Main> :k Poly
Poly :: * -> *
*Main> :t Poly
Poly :: [b] -> Poly [b]
*Main> case Poly [1,2,3] of _ -> 0
0
*Main> case Poly 4 of _ -> 0

<interactive>:1:10:
    No instance for (Num [b])
      arising from the literal `4' at <interactive>:1:10
    Possible fix: add an instance declaration for (Num [b])
    In the first argument of `Poly', namely `4'
    In the scrutinee of a case expression: Poly 4
    In the expression: case Poly 4 of _ -> 0
*Main> case Poly True of _ -> 0

<interactive>:1:10:
    Couldn't match expected type `[b]' against inferred type `Bool'
    In the first argument of `Poly', namely `True'
    In the scrutinee of a case expression: Poly True
    In the expression: case Poly True of _ -> 0

现在我们可以尝试为这种类型编写一个 Functor 实例：

instance Functor Poly where
  fmap f (Poly x) = Poly (f x)

Couldn't match expected type `[b1]' against inferred type `b2'
  `b2' is a rigid type variable bound by
       the type signature for `fmap' at <no location info>
In the first argument of `Poly', namely `(f x)'
In the expression: Poly (f x)
In the definition of `fmap': fmap f (Poly x) = Poly (f x)

这是行不通的。有趣的是，我们甚至无法真正编写 myMap：

polymap f (Poly x) = Poly (f x)

如果我们尝试这样做，我们会得到

GADT pattern match in non-rigid context for `Poly'
  Tell GHC HQ if you'd like this to unify the context
In the pattern: Poly x
In the definition of `polymap': polymap f (Poly x) = Poly (f x)

当然我们可以使用类型注释来修复它：

 polymap :: ([a] -> [b]) -> Poly [a] -> Poly [b]

但如果没有它，这与 fmap 遇到的问题类似。 Functor 只是没有任何地方可以输出“我保证总是使用列表”的额外上下文，事实上它确实不能。例如，您始终可以说 undefined :: Poly Int 。简而言之，我不认为真的有一个习语可以表达这一点（实际上，有人可能会提供足够的 ghc 扩展魔法来做到这一点）。当然不是现有的。