haskell - 为什么类型安全的关系操作如此困难？

Question

我试图在 Haskell 中编写一个关系问题，但我不得不发现以类型安全的方式执行此操作远非显而易见。例如。谦虚的

select 1,a,b, from T

已经提出了一些问题:

这个函数的类型是什么？

投影的类型是什么1,a,b ?一般投影的类型是什么？

什么是结果类型，如何表达结果类型和投影之间的关系？

接受任何有效投影的这种函数的类型是什么？

如何在编译时检测无效预测？

如何将列添加到表格或投影中？

我相信即使是 Oracle 的 PL/SQL 语言也不能完全正确地做到这一点。虽然无效预测大多在编译时检测到，但大量类型错误仅在运行时显示。大多数其他与 RDBMS 的绑定(bind)(例如 Java 的 jdbc 和 perl 的 DBI)使用包含在字符串中的 SQL，因此完全放弃了类型安全。

进一步的研究表明，有一些 Haskell 库( HList、 vinyl 和 TRex)提供类型安全的可扩展记录等。但是这些库都需要 Haskell 扩展，如 DataKinds、FlexibleContexts 等等。此外，这些库并不容易使用并且有诡计的味道，至少对于像我这样的未初始化的观察者来说是这样。

这表明，类型安全的关系操作不适合函数范式，至少不像在 Haskell 中实现的那样。

我的问题如下:

以类型安全的方式对关系操作建模困难的根本原因是什么？ Hindley-Milner 的不足之处在哪里？或者问题是否已经起源于类型化的 lambda 演算？

有没有一种范式，关系操作是一等公民？如果是这样，是否有现实世界的实现？

Answer 1

让我们将在某些列上索引的表定义为具有两个类型参数的类型:

data IndexedTable k v = ???

groupBy :: (v -> k) -> IndexedTable k v

-- A table without an index just has an empty key
type Table = IndexedTable ()

k将是表索引的所有列的(可能是嵌套的)元组。 v将是表未索引的所有列的(可能是嵌套的)元组。

因此，例如，如果我们有下表

| Id | First Name | Last Name |
|----|------------|-----------|
|  0 | Gabriel    | Gonzalez  |
|  1 | Oscar      | Boykin    |
|  2 | Edgar      | Codd      |

...并且它在第一列上被索引，那么类型将是:

type Id = Int
type FirstName = String
type LastName = String

IndexedTable Int (FirstName, LastName)

但是，如果它在第一列和第二列上被索引，那么类型将是:

IndexedTable (Int, Firstname) LastName

Table将实现 Functor , Applicative , 和 Alternative类型类。换句话说:

instance Functor (IndexedTable k)

instance Applicative (IndexedTable k)

instance Alternative (IndexedTable k)

所以连接将被实现为:

join :: IndexedTable k v1 -> IndexedTable k v2 -> IndexedTable k (v1, v2)
join t1 t2 = liftA2 (,) t1 t2

leftJoin :: IndexedTable k v1 -> IndexedTable k v2 -> IndexedTable k (v1, Maybe v2)
leftJoin t1 t2 = liftA2 (,) t1 (optional t2)

rightJoin :: IndexedTable k v1 -> IndexedTable k v2 -> IndexedTable k (Maybe v1, v2)
rightJoin t1 t2 = liftA2 (,) (optional t1) t2

然后你会有一个单独的类型，我们称之为 Select .此类型还将有两个类型参数:

data Select v r = ???

一个 Select会消耗一堆 v 类型的行从表中生成 r 类型的结果.换句话说，我们应该有一个类型的函数:

selectIndexed :: Indexed k v -> Select v r -> r

一些例子 Select我们可能定义的 s 是:

count   :: Select v Integer
sum     :: Num a => Select a a
product :: Num a => Select a a
max     :: Ord a => Select a a

这个 Select类型将实现 Applicative接口(interface)，所以我们可以组合多个 Select s 成单个 Select .例如:

liftA2 (,) count sum :: Select Integer (Integer, Integer)

这将类似于此 SQL:

SELECT COUNT(*), SUM(*)

然而，我们的表通常会有多个列，所以我们需要一种方法来关注 Select到单个列上。我们称这个函数为 Focus :

focus :: Lens' a b -> Select b r -> Select a r

这样我们就可以编写如下内容:

liftA3 (,,) (focus _1 sum) (focus _2 product) (focus _3 max)
  :: (Num a, Num b, Ord c)
  => Select (a, b, c) (a, b, c)

所以如果我们想写这样的东西:

SELECT COUNT(*), MAX(firstName) FROM t

这相当于这个 Haskell 代码:

firstName :: Lens' Row String

table :: Table Row

select table (liftA2 (,) count (focus firstName max)) :: (Integer, String)

所以你可能想知道如何实现 Select和 Table .

我描述了如何实现 Table在这篇文章中:

http://www.haskellforall.com/2014/12/a-very-general-api-for-relational-joins.html

...你可以实现 Select就像:

type Select = Control.Foldl.Fold

type focus = Control.Foldl.pretraverse

-- Assuming you define a `Foldable` instance for `IndexedTable`
select t s = Control.Foldl.fold s t

另外，请记住，这些并不是实现 Table 的唯一方法。和 Select .它们只是一个简单的实现，可以帮助您入门，您可以根据需要对其进行概括。

从表中选择列怎么样？好吧，你可以定义:

column :: Select a (Table a)
column = Control.Foldl.list

所以如果你想做:

SELECT col FROM t

...你会写:

field :: Lens' Row Field

table :: Table Row

select (focus field column) table :: [Field]

重要的一点是，您可以在 Haskell 中很好地实现关系 API，而无需任何花哨的类型系统扩展。