时间戳

首页 > 解决方案 > 表示满足多个约束的任何类型的实例

haskell - 表示满足多个约束的任何类型的实例

问题描述

我怀疑所有适用的、可折叠的幺半群都可以以相同的方式遍历。换句话说，对于t :: * -> *满足Applicative和的任何类型，Foldable并且所有实例化都t a满足Monoid，都有 的自由实例Traversable。

这是我将如何实施sequenceA：

sequenceA :: (Applicative t, Foldable t, Monoid (t a), Applicative f) =>
  t (f a) -> f (t a)
sequenceA = foldl (liftA2 $ \b a -> mappend b (pure a)) (pure mempty)

例如，我们可以使用它来将包含函数的列表遍历到将产生列表的函数中（因为[]它是可应用的、可折叠的，并且对于所有类型都是一个幺半群[a]）：

sequenceA [\a -> 2 * a, \a -> 2 + a] $ 5
-- [10, 7]

不幸的是，我无法弄清楚如何Traversable使用sequenceA. 这是我尝试过的：

instance (Applicative t, Foldable t, Monoid (t a)) => Traversable t where
  sequenceA = foldl (liftA2 $ \b a -> mappend b (pure a)) (pure mempty)

如果我尝试在没有任何扩展的情况下编译它，我会得到：

<interactive>:3:55: error:
    • Illegal instance declaration for ‘Traversable t’
        (All instance types must be of the form (T a1 ... an)
         where a1 ... an are *distinct type variables*,
         and each type variable appears at most once in the instance head.
         Use FlexibleInstances if you want to disable this.)
    • In the instance declaration for ‘(Traversable t)’

我在 Haskell 中表达这个实例的正确方法是什么？

如果递归添加编译器错误提到的任何扩展可能会解决问题，我尝试了这一点并将结果粘贴到此处。如果有任何相关的错误消息，请告诉我，我会将它们直接移动到问题正文中。

标签： haskelltypeclass

解决方案

你的猜想是错误的。考虑类型

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import Data.Semigroup
import Data.Monoid hiding ((<>))

newtype FL a = FL [a] deriving (Functor, Foldable, Applicative)
instance Semigroup (FL a) where
  FL as <> FL bs = FL $ as ++ drop (length as) bs
instance Monoid (FL a) where
  mempty = FL []
  mappend = (<>)

这是基于Alternative. 显然是 的标识，并且关联性不太明显，因此它是一个有效的实例。但是，它不会导致使用您的定义的有效实例。您的定义适用于列表（以及其他一些类型，例如and ），因为它们具有非常特殊的结构。ZipListmemptymappendmappendMonoidTraversableData.Sequence.SeqData.Vector.Vector

特别地，[a]是（以一些惰性考虑为模）具有并满足特定通用属性的自由幺半群：apurefoldMap

无论何时m是 a Monoid，f :: a -> m是foldMap f唯一的幺半群同态 使得foldMap f . pure = f。

在其他情况下，例如FL上面，您通常不会最终满足 的恒等律Traversable，尽管我想您可能会发现它在某些较弱的条件下起作用。

无论如何，如果你想搞砸你的想法怎么办？最简单的事情是用约束替换Monoid (t a)约束Alternative t。然后你可以使用emptyinstead ofmempty和(<|>)instead of mappend，并且类型（尽管不是法律）应该可以解决。

如果你真的坚持下去Monoid，你必须从Data.Constraint.Forall. 你想说的是，对于每个a, Monoid (t a)。您可以将其表示为ForallF Monoid t。但是您不能只Monoid在该约束下使用方法，因为GHC. 相反，您必须使用instF：

{-# LANGUAGE TypeOperators, ScopedTypeVariables, InstanceSigs, ... #-}

import Data.Constraint
import Data.Constraint.Forall

instance (Applicative t, Foldable t, ForallF Monoid t)
  => Traversable t where
  sequenceA :: forall f a. Applicative f => t (f a) -> f (t a)
  sequenceA =
   case instF :: ForallF Monoid t :- Monoid (t a) of
     Sub Dict -> foldl (liftA2 $ \b a -> mappend b (pure a)) (pure mempty)

当然，一旦你遇到了所有这些麻烦，你会发现你的实例与其他Traversable实例重叠，这几乎是一场彻底的灾难。 Traversable

附录：正如Benjamin Hodgson 所指出的，有一个公认的GHC 提案来支持量化（和暗示）约束。当它实现时（可能很快），您将能够简单地编写forall a. Monoid (t a)为约束，并且事情应该更容易解决。

推荐阅读