有效图的类型可以在 Dhall 中编码吗？

Question

我想在 Dhall 中表示一个 wiki（一组包含有向图的文档）。这些文档将呈现给 HTML，我想防止生成损坏的链接。正如我所见，这可以通过使无效图形（链接到不存在节点的图形）无法通过类型系统表示或通过将函数写入 return 任何可能图形中的错误列表（例如"In possible graph X, Node A contains a link to a non-existent Node B").

一个朴素的邻接表表示可能看起来像这样：

let Node : Type = {
    id: Text,
    neighbors: List Text
}
let Graph : Type = List Node
let example : Graph = [
    { id = "a", neighbors = ["b"] }
]
in example

正如这个例子所表明的那样，这种类型接受与有效图不对应的值（没有 id 为 "b" 的节点，但是 id 为 "a" 的节点规定了一个邻居ID "b"）。而且，不可能通过折叠每个Node的邻居来生成这些问题的列表，因为Dhall在设计上不支持字符串比较。

是否有任何表示形式允许计算损坏链接列表或通过类型系统排除损坏链接？

更新：我刚刚发现 Naturals 在 Dhall 中具有可比性。所以我想可以编写一个函数来识别任何无效边（"broken links"）和标识符的重复使用，如果标识符是 Naturals。

不过，是否可以定义图形类型的原始问题仍然存在。

Answer 1

是的，您可以在 Dhall 中为类型安全、有向、可能循环的图建模，如下所示：

let List/map =
      https://prelude.dhall-lang.org/v14.0.0/List/map sha256:dd845ffb4568d40327f2a817eb42d1c6138b929ca758d50bc33112ef3c885680

let Graph
    : Type
    =     forall (Graph : Type)
      ->  forall  ( MakeGraph
                  :     forall (Node : Type)
                    ->  Node
                    ->  (Node -> { id : Text, neighbors : List Node })
                    ->  Graph
                  )
      ->  Graph

let MakeGraph
    :     forall (Node : Type)
      ->  Node
      ->  (Node -> { id : Text, neighbors : List Node })
      ->  Graph
    =     \(Node : Type)
      ->  \(current : Node)
      ->  \(step : Node -> { id : Text, neighbors : List Node })
      ->  \(Graph : Type)
      ->  \ ( MakeGraph
            :     forall (Node : Type)
              ->  Node
              ->  (Node -> { id : Text, neighbors : List Node })
              ->  Graph
            )
      ->  MakeGraph Node current step

let -- Get `Text` label for the current node of a Graph
    id
    : Graph -> Text
    =     \(graph : Graph)
      ->  graph
            Text
            (     \(Node : Type)
              ->  \(current : Node)
              ->  \(step : Node -> { id : Text, neighbors : List Node })
              ->  (step current).id
            )

let -- Get all neighbors of the current node
    neighbors
    : Graph -> List Graph
    =     \(graph : Graph)
      ->  graph
            (List Graph)
            (     \(Node : Type)
              ->  \(current : Node)
              ->  \(step : Node -> { id : Text, neighbors : List Node })
              ->  let neighborNodes
                      : List Node
                      = (step current).neighbors

                  let nodeToGraph
                      : Node -> Graph
                      =     \(node : Node)
                        ->  \(Graph : Type)
                        ->  \ ( MakeGraph
                              :     forall (Node : Type)
                                ->  forall (current : Node)
                                ->  forall  ( step
                                            :     Node
                                              ->  { id : Text
                                                  , neighbors : List Node
                                                  }
                                            )
                                ->  Graph
                              )
                        ->  MakeGraph Node node step

                  in  List/map Node Graph nodeToGraph neighborNodes
            )

let {- Example node type for a graph with three nodes

           For your Wiki, replace this with a type with one alternative per document
        -}
    Node =
      < Node0 | Node1 | Node2 >

let {- Example graph with the following nodes and edges between them:

                       Node0 ↔ Node1
                         ↓
                       Node2
                         ↺

           The starting node is Node0
        -}
    example
    : Graph
    = let step =
                \(node : Node)
            ->  merge
                  { Node0 = { id = "0", neighbors = [ Node.Node1, Node.Node2 ] }
                  , Node1 = { id = "1", neighbors = [ Node.Node0 ] }
                  , Node2 = { id = "2", neighbors = [ Node.Node2 ] }
                  }
                  node

      in  MakeGraph Node Node.Node0 step

in  assert : List/map Graph Text id (neighbors example) === [ "1", "2" ]

此表示保证没有断边。

我也把这个答案变成了一个你可以使用的包：

https://github.com/Gabriel439/graph

编辑： 以下是相关资源和附加解释，可以帮助阐明正在发生的事情：

首先，从下面的 Haskell 类型开始 tree:

data Tree a = Node { id :: a, neighbors :: [ Tree a ] }

您可以将此类型视为一种惰性且可能无限的数据结构，表示如果您一直访问邻居就会得到什么。

现在，让我们假设上面的 Tree 表示实际上是我们的 Graph，只需将数据类型重命名为 Graph:

data Graph a = Node { id :: a, neighbors :: [ Graph a ] }

...但是即使我们想使用这种类型，我们也没有办法在 Dhall 中直接对该类型建模，因为 Dhall 语言不提供对递归数据结构的内置支持。那我们怎么办？

幸运的是，实际上有一种方法可以在像 Dhall 这样的非递归语言中嵌入递归数据结构和递归函数。其实有两种方法！

F-algebras - 用于实现递归
F-coalgebras - 用于实现"corecursion"

我首先读到的是 Wadler 的以下草稿 post：

Recursive types for free!

...但我可以使用以下两种 Haskell 类型来总结基本思想：

{-# LANGUAGE RankNTypes #-}

-- LFix is short for "Least fixed point"
newtype LFix f = LFix (forall x . (f x -> x) -> x)

...和：

{-# LANGUAGE ExistentialQuantification #-}

-- GFix is short for "Greatest fixed point"
data GFix f = forall x . GFix x (x -> f x)

LFix 和 GFix 的工作方式是您可以给它们 "one layer" 您想要的递归或 "corecursive" 类型（即 f ) 然后他们会为您提供与所需类型一样强大的东西，而无需递归或核心递归的语言支持。

让我们以列表为例。我们可以使用以下 ListF 类型对列表的 "one layer" 进行建模：

-- `ListF` is short for "List functor"
data ListF a next = Nil | Cons a next

将该定义与我们通常使用普通递归数据类型定义定义 OrdinaryList 的方式进行比较：

data OrdinaryList a = Nil | Cons a (OrdinaryList a)

主要区别在于 ListF 采用一个额外的类型参数 (next)，我们将其用作该类型所有 recursive/corecursive 次出现的占位符。

现在，有了ListF，我们可以这样定义递归和核心递归列表：

type List a = LFix (ListF a)

type CoList a = GFix (ListF a)

... 其中：

List是一个递归列表，在没有语言支持递归的情况下实现
CoList 是在没有语言支持的情况下实现的 corecursive 列表

这两种类型都等同于("isomorphic to")[]，意思是：

可以在List和[]之间来回转换
你可以在CoList和[]之间来回转换

让我们通过定义那些转换函数来证明这一点！

fromList :: List a -> [a]
fromList (LFix f) = f adapt
  where
    adapt (Cons a next) = a : next
    adapt  Nil          = []

toList :: [a] -> List a
toList xs = LFix (\k -> foldr (\a x -> k (Cons a x)) (k Nil) xs)

fromCoList :: CoList a -> [a]
fromCoList (GFix start step) = loop start
  where
    loop state = case step state of
        Nil           -> []
        Cons a state' -> a : loop state'

toCoList :: [a] -> CoList a
toCoList xs = GFix xs step
  where
    step      []  = Nil
    step (y : ys) = Cons y ys

所以实现Dhall类型的第一步是转换递归Graph类型：

data Graph a = Node { id :: a, neighbors :: [ Graph a ] }

... 到等效的共同递归表示：

data GraphF a next = Node { id ::: a, neighbors :: [ next ] }

data GFix f = forall x . GFix x (x -> f x)

type Graph a = GFix (GraphF a)

...虽然为了稍微简化类型，我发现将 GFix 专门化到 f = GraphF:

的情况更容易

data GraphF a next = Node { id ::: a, neighbors :: [ next ] }

data Graph a = forall x . Graph x (x -> GraphF a x)

Haskell 没有像 Dhall 这样的匿名记录，但如果有，我们可以通过内联 GraphF:

的定义进一步简化类型

data Graph a = forall x . MakeGraph x (x -> { id :: a, neighbors :: [ x ] })

现在这开始看起来像 Graph 的 Dhall 类型，特别是如果我们将 x 替换为 node:

data Graph a = forall node . MakeGraph node (node -> { id :: a, neighbors :: [ node ] })

然而，还有最后一个棘手的部分，即如何将 ExistentialQuantification 从 Haskell 翻译成 Dhall。事实证明，您始终可以使用以下等价将存在量化转换为全称量化（即 forall）：

exists y . f y ≅ forall x . (forall y . f y -> x) -> x

我相信这叫做"skolemization"

有关详细信息，请参阅：

Wikipedia - Existential Quantification

...最后的技巧为您提供了 Dhall 类型：

let Graph
    : Type
    =     forall (Graph : Type)
      ->  forall  ( MakeGraph
                  :     forall (Node : Type)
                    ->  Node
                    ->  (Node -> { id : Text, neighbors : List Node })
                    ->  Graph
                  )
      ->  Graph

... 其中 forall (Graph : Type) 与上一个公式中的 forall x 的作用相同， forall (Node : Type) 与上一个公式中的 forall y 的作用相同。

有效图的类型可以在 Dhall 中编码吗？

Can the type of valid graphs be encoded in Dhall?

graph

adjacency-list

dhall