首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >有哪些类型级编程的例子?

问有哪些类型级编程的例子?
EN

Stack Overflow用户
提问于 2014-06-30 07:18:35
回答 3查看 9.2K关注 0票数 36

我不明白“类型级编程”是什么意思,我也不能用Google找到合适的解释。

谁能提供一个演示类型级编程的示例?对范例的解释和/或定义将是有用和值得赞赏的。

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2014-06-30 09:07:06

在大多数静态类型语言中,您有两个“域”:值级和类型级(有些语言甚至更多)。类型级编程涉及类型系统中的编码逻辑(通常是函数抽象),这在编译时进行计算。例如模板元编程或Haskell类型族。

在Haskell中需要一些语言扩展来完成这个示例,但是现在您可以忽略它们,只将类型族看作是一个函数,但是基于类型级别的数字(Nat)。

代码语言:javascript
复制
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}

import GHC.TypeLits
import Data.Proxy

-- value-level
odd :: Integer -> Bool
odd 0 = False
odd 1 = True
odd n = odd (n-2)

-- type-level
type family Odd (n :: Nat) :: Bool where
    Odd 0 = False
    Odd 1 = True
    Odd n = Odd (n - 2)

test1 = Proxy :: Proxy (Odd 10)
test2 = Proxy :: Proxy (Odd 11)

在这里,我们不是测试一个自然数值是否为奇数,而是测试一个自然数类型是否为奇数,并在编译时将其简化为一个类型级别的布尔值。如果您评估此程序,test1和test2的类型将在编译时计算为:

代码语言:javascript
复制
λ: :type test1
test1 :: Proxy 'False
λ: :type test2
test2 :: Proxy 'True

这是类型级编程的本质,根据语言的不同,您可以在类型级编码复杂的逻辑,这些逻辑有多种用途。例如,在值级限制某些行为,管理资源终结,或存储有关数据结构的更多信息。

票数 32
EN

Stack Overflow用户

发布于 2014-06-30 09:06:32

您已经熟悉了“值级”编程,通过它可以操作诸如42 :: Int或'a' :: Char之类的值。在诸如Haskell、Scala和许多其他语言中,类型级编程允许您操作诸如Int :: *或Char :: *之类的类型,其中*是一种具体类型(Maybe a或[a]是具体类型,但不是Maybe或[],它们具有友好的* -> *)。

考虑这个函数

代码语言:javascript
复制
foo :: Char -> Int
foo x = fromEnum x

在这里,foo接受Char类型的值,并使用Int的Enum实例返回Char类型的新值。此函数用于操作值。

现在将foo与这个通过TypeFamilies语言扩展启用的类型族进行比较。

代码语言:javascript
复制
type family Foo (x :: *)
type instance Foo Char = Int

在这里,Foo接受一种类型的*,并使用简单的映射*返回一种新的类型Char -> Int。这是一个操作类型的类型级函数。

这是一个非常简单的例子,你可能想知道这怎么可能有用。使用更强大的语言工具,我们可以开始在类型级别对代码正确性的证明进行编码(有关这方面的更多信息,请参阅Curry-Howard通信)。

一个实际的例子是红黑树,它使用类型级编程来静态地保证树的不变量成立。

红黑树具有以下简单属性:

  1. 节点是红色或黑色的。
  2. 根是黑色的。
  3. 所有的叶子都是黑色的。(所有叶子的颜色都与根相同。)
  4. 每个红色节点必须有两个黑子节点。从给定节点到其任何后代叶子的每条路径都包含相同数量的黑色节点。

我们将使用DataKinds和GADTs,这是一个非常强大的类型级编程组合。

代码语言:javascript
复制
{-# LANGUAGE DataKinds, GADTS, KindSignatures #-}

import GHC.TypeLits

首先,一些类型来表示颜色。

代码语言:javascript
复制
data Colour = Red | Black -- promoted to types via DataKinds

这定义了一种新的由两种类型居住的Colour:Red和Black。请注意,这些类型中没有值(忽略底部),但无论如何我们都不需要它们。

红黑树节点由以下GADT表示

代码语言:javascript
复制
-- 'c' is the Colour of the node, either Red or Black
-- 'n' is the number of black child nodes, a type level Natural number
-- 'a' is the type of the values this node contains
data Node (c :: Colour) (n :: Nat) a where
    -- all leaves are black
    Leaf :: Node Black 1 a
    -- black nodes can have children of either colour
    B    :: Node l     n a -> a -> Node r     n a -> Node Black (n + 1) a
    -- red nodes can only have black children
    R    :: Node Black n a -> a -> Node Black n a -> Node Red n a

GADT允许我们在类型中直接表达R和B构造函数的Colour。

树的根看起来像这样

代码语言:javascript
复制
data RedBlackTree a where
    RBTree :: Node Black n a -> RedBlackTree a

现在,不可能创建违反上述4个属性中的任何一个的类型良好的RedBlackTree。

  1. 第一个约束显然是真的,只有两种类型存在于RedBlackTree中,根的定义是黑色的,
  2. 从Leaf构造函数的定义来看,所有的叶子都是黑色的。
  3. 从R构造函数的定义来看,它的两个子节点必须是Black节点。同样,每个子树的黑子节点的数量是相等的(在左子树和右子树的类型中使用相同的n )

所有这些条件都是在编译时由GHC检查的,这意味着我们永远不会从一些行为不端的代码中获得运行时异常,这些代码会使我们对红黑树的假设无效。重要的是,没有与这些额外好处相关的运行时成本,所有的工作都是在编译时完成的。

票数 36
EN

Stack Overflow用户

发布于 2014-06-30 13:18:24

其他的答案都很好,但我想强调一点。我们的编程语言术语理论是基于Lambda演算的。一个“纯粹的”Lisp相当于(或多或少)一个高度糖化的无类型Lambda演算。程序的含义由评估规则定义,该规则说明当程序运行时Lambda微积分项如何减少。

在类型化语言中,我们为术语分配类型。对于每个评估规则,我们都有一个相应的类型规则,它显示了类型是如何通过评估保留的。根据类型系统的不同,还有其他规则定义类型之间的关系。事实证明,一旦你得到了一个足够有趣的类型系统,这些类型及其规则系统也对应于Lambda演算的一个变体!

虽然现在人们普遍认为Lambda演算是一种编程语言,但它最初是作为一种逻辑系统设计的。这就是为什么它对于在编程语言中推理术语的类型很有用。但是Lambda演算的编程语言方面允许编写由类型检查器计算的程序。

希望您现在可以看到,“类型级编程”与“术语级编程”并没有本质上的不同,只是现在在类型系统中拥有一种强大到足以让您有理由用它编写程序的语言并不是很常见。

票数 15
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/24481113

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档