为什么长度为包含2个元素的元组返回1,并为具有更多元素的元组提供错误？

Question

我正在使用" 第一原理的Haskell编程 " 一书来学习Haskell ,并且在第4章"基本数据类型"的末尾,我遇到了让我感到困惑的事情.这本书提到了一个功能,length并说它适用于Listss.一切都很好,但是当我length用各种Tuples 尝试这个功能时,我看到的东西让我很困惑:

首先,让我们看看类型length:

:t length
length :: Foldable t => t a -> Int

好的,所以我在上面读到"带一个可折叠的,我认为这是一个方便的列表,并返回一个Int,即列表中元素的数量." 因此,我的第一个困惑:为什么以下工作:

length (1, 1)
1

因为对我而言,似乎我刚刚传递了一个带有两个元素的元组length,它返回1.是元组列表吗？元组是否可折叠？当然,为什么1呢？

现在我更进一步:

length (1, 1, 1)

<interactive>:6:1:
    No instance for (Foldable ((,,) t0 t1))
      arising from a use of ‘length’
    In the expression: length (1, 1, 1)
    In an equation for ‘it’: it = length (1, 1, 1)

<interactive>:6:9:
    No instance for (Num t0) arising from the literal ‘1’
    The type variable ‘t0’ is ambiguous
    Note: there are several potential instances:
      instance Num Integer -- Defined in ‘GHC.Num’
      instance Num Double -- Defined in ‘GHC.Float’
      instance Num Float -- Defined in ‘GHC.Float’
      ...plus two others
    In the expression: 1
    In the first argument of ‘length’, namely ‘(1, 1, 1)’
    In the expression: length (1, 1, 1)

<interactive>:6:12:
    No instance for (Num t1) arising from the literal ‘1’
    The type variable ‘t1’ is ambiguous
    Note: there are several potential instances:
      instance Num Integer -- Defined in ‘GHC.Num’
      instance Num Double -- Defined in ‘GHC.Float’
      instance Num Float -- Defined in ‘GHC.Float’
      ...plus two others
    In the expression: 1
    In the first argument of ‘length’, namely ‘(1, 1, 1)’
    In the expression: length (1, 1, 1)

另一个尝试:

length (1::Int, 1::Int, 1::Int)

<interactive>:7:1:
    No instance for (Foldable ((,,) Int Int))
      arising from a use of ‘length’
    In the expression: length (1 :: Int, 1 :: Int, 1 :: Int)
    In an equation for ‘it’: it = length (1 :: Int, 1 :: Int, 1 :: Int)

但以下工作:

length (1::Int, 1::Int)
1

对于我上面观察到的行为有什么好的解释吗？我误读了这种类型length吗？或者幕后还有其他事情发生了吗？

Answer 1

你遇到了一个Haskell 原因célèbre引起了很多讨论和咬牙切齿.

基本上,对于的目的Foldable(即提供类型类length),2元组不被认为是两种元素的容器,但容器一个元件伴随着一些上下文.

您可以a从any中提取类型元素的列表Foldable a.请注意,对于2元组,类型变量Foldable是元组的第二个元素的类型变量,它可以与第一个元素的类型不同.

如果你有一个('c',2) :: (Char,Int)元组,那么Int在这种情况下你无法提取两个s就不足为奇了!但是当类型相同时,它就变得令人困惑.

至于为什么length (1::Int, 1::Int, 1::Int)失败,3元组没有Foldable定义实例,但也许它们应该有一个,以保持一致性.3元组的长度也为1.

顺便说一下,Identity可以被认为是一种1元组的仿函数Foldable当然也有1长度.

应Foldable元组实例中存在的一切？我认为赞成肯定的基本哲学是,我们称之为"充实".如果类型可以以明确定义的合法方式成为类型类的实例,那么它应该具有该实例.即使它似乎没有用,在某些情况下,也可能令人困惑.

Answer 2

我喜欢danidiaz的答案,因为它提供了关于Foldable元组实例如何工作以及它直观意味着什么的高层次直觉.然而,它的机制似乎仍然存在一些混乱; 所以在这个答案中,我将重点关注"幕后"比特.相关Foldable实例的全文可在线获取,如下所示:

instance Foldable ((,) a) where
    foldMap f (_, y) = f y
    foldr f z (_, y) = f y z

您已经可以从这个实例中看到,在所有方法中,每个元组的第一部分都被完全忽略Foldable.但是,要完成的图片,我们需要看的定义minimum和length.因为这种情况下不包括定义minimum和length,我们应该看看这些默认定义.Foldable看起来像这样的类声明(不相关的位被省略):

class Foldable t where
    length :: t a -> Int
    length = foldl' (\c _ -> c+1) 0

    foldl' :: (b -> a -> b) -> b -> t a -> b
    foldl' f z0 xs = foldr f' id xs z0
      where f' x k z = k $! f z x

    minimum :: forall a . Ord a => t a -> a
    minimum = fromMaybe (error "minimum: empty structure") .
       getMin . foldMap (Min #. (Just :: a -> Maybe a))

现在,让我们扩展这些定义,看看他们从哪里获得.

length (a, b)
= { definition of length }
foldl' (\c _ -> c+1) 0 (a, b)
= { definition of foldl' }
foldr (\x k z -> k $! (\c _ -> c+1) z x) id (a, b) 0
= { definition of foldr }
(\x k z -> k $! (\c _ -> c+1) z x) b id 0
= { beta reduction }
id $! (\c _ -> c+1) 0 b
= { id $! e = e }
(\c _ -> c+1) 0 b
= { beta reduction }
1

请注意,结论认为,无论是我们插上了a和b.现在让我们做minimum.对于我们而言,我们将替换(#.)与(.)-唯一不同的是效率,这是我们不关心的推理这一行.

minimum (a, b)
= { definition of minimum }
( fromMaybe (error "minimum: empty structure")
. getMin
. foldMap (Min . Just)
) (a, b)
= { definition of (.) }
( fromMaybe (error "minimum: empty structure")
. getMin
) (foldMap (Min . Just) (a, b))
= { definition of foldMap }
( fromMaybe (error "minimum: empty structure")
. getMin
) ((Min . Just) b)
= { definition of (.) }
fromMaybe (error "minimum: empty structure")
(getMin (Min (Just b)))
= { definition of getMin }
fromMaybe (error "minimum: empty structure") (Just b)
= { definition of fromMaybe }
b