0

这是一个（系列）Haskell 问题。我对 Haskell 相当陌生。

假设我们有一个 4 元组 (a1,a2,a3,a4)。我们如何定义一个函数，kth给出这个元组中的第 k 个元素？例子，

kth (1,"A",'b',True) 3 = 'b'

如果a1、a2、a3、a4的类型相同，那么它的定义就比较简单了。例如，如果它们都是整数：

kth :: (Int,Int,Int,Int) -> Int -> Int
kth (a1,a2,a3,a4) 1 = a1
kth (a1,a2,a3,a4) 2 = a2
kth (a1,a2,a3,a4) 3 = a3
kth (a1,a2,a3,a4) 4 = a4

我怀疑为什么这不简单是因为 Haskell 必须提前知道类型。在库函数fstandsnd中，Haskell 知道输出类型是形式的第一个元素的类型，输出类型是后者的第二个元素的类型。因此，没有歧义。在kth中，输出类型取决于第二个输入，因此 Haskell 无法根据语法进行类型检查。

现在，假设我们有一个第 n 个元组 (a1,a2,...,an)。我们可以定义一个长度函数族，使得

lengthTuple :: a -> Int
lengthTuple (a1,a2,...,an) = n
4

3 回答 3

1

如果索引必须是 ，则无法实现函数Int，但如果它是自定义“单例”索引类型，则可以。本质上，如果我们想模仿依赖类型，最好的选择是大量传递单例，将类型级别的值连接到术语级别的值。

这是一个例子：

{-# LANGUAGE GADTs, DataKinds, TypeFamilies #-}
{-# OPTIONS -Wall #-}

-- custom index type
data Ix = I1 | I2 | I3 | I4

-- associated singleton type (this could be autogenerated using the singletons library)
data SIx (ix :: Ix) where
  SI1 :: SIx 'I1
  SI2 :: SIx 'I2
  SI3 :: SIx 'I3
  SI4 :: SIx 'I4

-- type level function
type family T (ix :: Ix) a1 a2 a3 a4 
type instance T 'I1 a1 _ _ _ = a1
type instance T 'I2 _ a2 _ _ = a2
type instance T 'I3 _ _ a3 _ = a3
type instance T 'I4 _ _ _ a4 = a4

-- our "dependent" tuple selector
choose :: (a1, a2, a3, a4) -> SIx ix -> T ix a1 a2 a3 a4
choose (x1, _, _, _) SI1 = x1
choose (_, x2, _, _) SI2 = x2
choose (_, _, x3, _) SI3 = x3
choose (_, _, _, x4) SI4 = x4

如果需要，我们可以“隐藏”ix参数SIx ix并T ix a1 a2 a3 a4使用存在包装器（作为一种依赖求和类型），构建一个给定“某个索引”返回“某个组件”的函数。

如果我们有真正的依赖类型，这会方便得多。尽管如此，这是我们目前为在运行时进行类型擦除所付出的代价。如果 Haskell 有朝一日将非擦除pi a . ...类型添加到forall a . ...我们现在拥有的已擦除类型中，我们将拥有更多控制权。

于 2019-12-03T19:20:58.983 回答
1

这种问题（依赖类型）在 Haskell 中还是很头疼的。Prelude 中的元组不太适合这种任务（尽管可能可行）。但是对于这类问题，您可以使用具有依赖类型的大小向量。

示例： https ://www.schoolofhaskell.com/user/konn/prove-your-haskell-for-great-safety/dependent-types-in-haskell

于 2019-12-03T17:15:07.723 回答
0

正如一些评论中所建议的那样，简短的回答是，您不应该认真地在 Haskell 中执行此操作。如果您发现自己需要编写可以对不同大小的元组进行操作的函数，那么您在编程 Haskell 时是错误的。

然而，定义类似函数的惯用方法lengthTuple是使用具有不同元组大小的显式实例的类型类。如果这是针对库的，则选择一些上限并将实例写入该大小。一个合理的选择可能是 15 元组，因为这也是拥有Show实例的最大元组：

> (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)
(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)
> (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16)
<interactive>:72:1: error:
    • No instance for (Show ...

因此， for 的定义lengthTuple如下所示：

class Tuple a where lengthTuple :: a -> Int
instance Tuple (a,b) where lengthTuple _ = 2
instance Tuple (a,b,c) where lengthTuple _ = 3
instance Tuple (a,b,c,d) where lengthTuple _ = 4
...up to 15...

乏味，但相当标准。

值得注意的是，可以在lengthTuple没有任何样板的情况下使用Data.Data泛型进行编写。这些泛型提供了一种以相当通用的方式折叠代数数据类型结构的方法，您可以使用Const仿函数在计算字段数量时忽略数据类型的实际内容：

import Data.Data
import Data.Functor.Const
lengthTuple :: (Data a) => a -> Int
lengthTuple = getConst . gfoldl (\(Const n) _ -> Const (n+1))
                                (\_ -> Const 0)

这很好用，尽管没有直接的方法将其限制为元组，您可能会发现它的非元组返回值有些令人惊讶：

> lengthTuple (1,2,3,4)
4
> lengthTuple ""
0
> lengthTuple "what the heck?"
2

写作kth要困难得多。你的直觉是对的。因为表达式的类型kth tuple n取决于值而不是参数的类型，所以n不可能进行简单的定义。其他答案涵盖了几种方法。

于 2019-12-03T22:07:43.267 回答