Haskell中如何为A*节点类型类定义关联类型与常量？

我正在练习在Haskell中实现带关联类型和常量的类型类，目标是为A*搜索算法的节点定义类型类，该节点需要满足以下特性：

• 可与其他节点比较（实现Eq、Data.Hashable）
• 拥有neighbours函数，返回相邻节点列表
• 具备启发式函数，返回节点间的“距离”
• 上述距离为关联类型，需满足Num和Ord约束，不能硬编码为float这类固定类型
• 拥有代表“零”和“无穷大”的关联值

如果熟悉Rust的话，我想定义的类型类等价于这段Rust trait：

trait NavNode : Eq + Hash + Sized {
    type Distance: Ord + Add;
    
    const INFINITY: Self::Distance;
    const ZERO: Self::Distance;
    
    fn heuristic(a: Self, b: Self) -> Self::Distance;
    fn neighbors(self) -> Vec<Self>;
} 

我写出了下面的Haskell代码，但遇到了几个问题：无法约束关联类型Distance为Num和Ord；编译器不认可zero、infinity常量的定义，还报错提示Distance a应该是Distance a0：

{-# LANGUAGE TypeFamilies #-}

class (Eq a, Hashable a) => NavNode a where
    type Distance a :: * -- How to tell it it's Num, Ord?
    heuristic   :: a -> a -> Distance a
    neighbours  :: a -> [a]
    zero        :: Distance a
    infinity    :: Distance a

问题修复与正确实现 #

1. 为关联类型添加约束 #

要给关联类型Distance加上Num和Ord约束，直接在类的头部约束中明确即可：

{-# LANGUAGE TypeFamilies #-}
import Data.Hashable

class (Eq a, Hashable a, Num (Distance a), Ord (Distance a)) => NavNode a where
    type Distance a :: *
    heuristic   :: a -> a -> Distance a
    neighbours  :: a -> [a]
    zero        :: Distance a
    infinity    :: Distance a

2. 解决Distance a的歧义问题 #

编译器报错是因为默认情况下，类中的常量无法关联到类参数a。启用ScopedTypeVariables扩展后，a的作用域会覆盖整个类定义，编译器就能识别Distance a对应的是当前类实例的关联类型：

{-# LANGUAGE TypeFamilies, ScopedTypeVariables #-}
import Data.Hashable

class (Eq a, Hashable a, Num (Distance a), Ord (Distance a)) => NavNode a where
    type Distance a :: *
    heuristic   :: a -> a -> Distance a
    neighbours  :: a -> [a]
    zero        :: Distance a
    infinity    :: Distance a

3. 可选： injective 类型家族增强类型安全 #

如果需要确保每个节点类型对应唯一的距离类型，可以启用TypeFamilyDependencies扩展，定义 injective 的类型家族：

{-# LANGUAGE TypeFamilies, ScopedTypeVariables, TypeFamilyDependencies #-}
import Data.Hashable

class (Eq a, Hashable a, Num (Distance a), Ord (Distance a)) => NavNode a where
    type Distance a = d | d -> a  -- 每个距离类型对应唯一节点类型
    heuristic   :: a -> a -> Distance a
    neighbours  :: a -> [a]
    zero        :: Distance a
    infinity    :: Distance a

示例实例 #

以下是一个简单网格节点的实现示例：

data GridNode = GridNode Int Int deriving (Eq, Hashable, Show)

instance NavNode GridNode where
    type Distance GridNode = Int
    heuristic (GridNode x1 y1) (GridNode x2 y2) = abs (x1 - x2) + abs (y1 - y2)
    neighbours (GridNode x y) = [GridNode (x+1) y, GridNode (x-1) y, GridNode x (y+1), GridNode x (y-1)]
    zero = 0
    infinity = maxBound

内容的提问来源于stack exchange，提问作者Ethan McTague