haskell 用关联的类型和常量来表示类型类？

eimct9ow 于 2023-10-19 发布在其他

关注(0)|答案(1)|浏览(110)

我正在尝试解决如何在Haskell中实现类型类的关联类型和常量的概念。
作为实践，我尝试为A*节点创建一个类型类。一个节点具有给定的traits：

可以与其他节点（即实现Eq、Data.Hashable）
相关函数neighbours提供相邻节点的列表（即，neighbours :: Node -> [Node]）
有一个启发式函数，它提供了节点之间的“距离”。
前面提到的距离是排序的 * 关联类型 *，必须是Num和Ord。它不能简单地硬编码为使用float或类似的东西，因为“距离”的概念可能有不同的精度要求，甚至可以在2D整数网格上使用类似曼哈顿距离的东西。
具有“零”和“无限”距离的关联值（尽管“无限”可以定义为99999、INT32 MAX等）。这取决于用户期望的类型）。

对于那些像我一样熟悉rust的人来说，与我试图定义的类型类相同的特征是：

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>;
}

最接近于我所做的实现是这样的，但是我发现没有办法将相关的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

haskell

来源：https://stackoverflow.com/questions/76894696/expressing-a-typeclass-with-associated-types-and-constants

1条答案

按热度按时间

wb1gzix01#

这是一个编译代码的示例。为了简单起见，我删除了Hashable，但是您可以在真实的代码中重新添加它。

{-# LANGUAGE TypeFamilies, AllowAmbiguousTypes #-}

import Data.Kind

class (Eq a, Ord (Distance a), Num (Distance a)) => NavNode a where
    type Distance a :: Type -- The line above requires this to be Ord and Num
    heuristic   :: a -> a -> Distance a
    neighbours  :: a -> [a]
    zero        :: Distance a
    infinity    :: Distance a

-- Dummy instance: it's nonsense, but it shows the main ideas.
instance NavNode String where
    type Distance String = Int
    heuristic x y = abs (length x - length y)
    neighbours x = [x]
    zero = 0
    infinity = 1000

main :: IO ()
main = print (infinity @String)

请注意最后一行中的@String，这是强制性的，以便指定实际的示例。实际上，多个类型可以将Int作为它们的关联距离类型，因此我们必须指定它来消除歧义。

赞(0）回复(0）举报 2023-10-19

我来回答

haskell 用关联的类型和常量来表示类型类？

1条答案

相关问题

热门标签

最新问答