哈斯克尔:为拉链创建类型类
-
22-08-2019 - |
题
所以,我一直在阅读一些关于在Haskell的拉链模式(和其他功能的语言,我想)遍历和修改的数据结构,我认为这将是一个很好的机会,我磨练我的技能在Haskell中创建的类型,由于 的类可以提供通用的接口穿越我编写代码来,独立的数据结构的遍历。
我想我可能会需要两个类 - 一个用于根数据结构,以及一个用于创建的特殊数据结构 遍历第一:
module Zipper where
class Zipper z where
go'up :: z -> Maybe z
go'down :: z -> Maybe z
go'left :: z -> Maybe z
go'right :: z -> Maybe z
class Zippable t where
zipper :: (Zipper z) => t -> z
get :: (Zipper z) => z -> t
put :: (Zipper z) => z -> t -> z
但是,当我试图这些用一些简单的数据结构等的列表:
-- store a path through a list, with preceding elements stored in reverse
data ListZipper a = ListZipper { preceding :: [a], following :: [a] }
instance Zipper (ListZipper a) where
go'up ListZipper { preceding = [] } = Nothing
go'up ListZipper { preceding = a:ps, following = fs } =
Just $ ListZipper { preceding = ps, following = a:fs }
go'down ListZipper { following = [] } = Nothing
go'down ListZipper { preceding = ps, following = a:fs } =
Just $ ListZipper { preceding = a:ps, following = fs }
go'left _ = Nothing
go'right _ = Nothing
instance Zippable ([a]) where
zipper as = ListZipper { preceding = [], following = as }
get = following
put z as = z { following = as }
或二进制树:
-- binary tree that only stores values at the leaves
data Tree a = Node { left'child :: Tree a, right'child :: Tree a } | Leaf a
-- store a path down a Tree, with branches not taken stored in reverse
data TreeZipper a = TreeZipper { branches :: [Either (Tree a) (Tree a)], subtree :: Tree a }
instance Zipper (TreeZipper a) where
go'up TreeZipper { branches = [] } = Nothing
go'up TreeZipper { branches = (Left l):bs, subtree = r } =
Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } }
go'up TreeZipper { branches = (Right r):bs, subtree = l } =
Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } }
go'down TreeZipper { subtree = Leaf a } = Nothing
go'down TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } =
Just $ TreeZipper { branches = (Right r):bs, subtree = l }
go'left TreeZipper { branches = [] } = Nothing
go'left TreeZipper { branches = (Right r):bs } = Nothing
go'left TreeZipper { branches = (Left l):bs, subtree = r } =
Just $ TreeZipper { branches = (Right r):bs, subtree = l }
go'right TreeZipper { branches = [] } = Nothing
go'right TreeZipper { branches = (Left l):bs } = Nothing
go'right TreeZipper { branches = (Right r):bs, subtree = l } =
Just $ TreeZipper { branches = (Left l):bs, subtree = r }
instance Zippable (Tree a) where
zipper t = TreeZipper { branches = [], subtree = t }
get TreeZipper { subtree = s } = s
put z s = z { subtree = s }
我无法得到它来编译,我只是得到了很多错误,这样,我的每个Zippable
实例定义:
Zipper.hs:28:14: Couldn't match expected type `z' against inferred type `ListZipper a' `z' is a rigid type variable bound by the type signature for `zipper' at Zipper.hs:10:20 In the expression: ListZipper {preceding = [], following = as} In the definition of `zipper': zipper as = ListZipper {preceding = [], following = as} In the definition for method `zipper'
所以我不知道在哪里何去何从。我怀疑我的问题是,我想这两个实例绑定
一起,当(Zipper z) =>
声明只想z
是任何Zipper
。
解决方案
(旁白:。你go'up
命名方案是......创造性的Haskell风格通常是驼峰)
您是在正确的轨道上。什么你写等同于下面。
{-# LANGUAGE RankNTypes #-}
instance Zippable [a] where
zipper = ... :: forall z. (Zipper z) => [a] -> z
get = ... :: forall z. (Zipper z) => z -> [a]
set = ... :: forall z. (Zipper z) => z -> [a] -> z
(对于所有类型的z
,给出Zipper z
,存在zipper :: [a] -> z
。)
您正在特林限定zipper = ... :: [a] -> ListZipper a
,这显然是过于严格。
您的代码将用下面的最小的变化类型检查:
{-# LANGUAGE MultiParamTypeClasses #-}
class (Zipper z) => Zippable z t where
zipper :: t -> z
get :: z -> t
set :: z -> t -> z
instance Zippable (ListZipper a) [a] where
...
instance Zippable (TreeZipper a) (Tree a) where
...
请参阅多参数类型类的。它是一个后Haskell'98扩展,但Haskell中实现广泛支持。
其他提示
您也可以使用类型同义词家庭代替多参数类型的类和函数依赖。在这样的情况下,他们提供一个更清洁,更容易理解的解决方案。在这种情况下,类和实例将变成:
class Zippable t where
type ZipperType t :: *
enter :: t -> ZipperType t
focus :: ZipperType t -> t
instance Zippable [a] where
type ZipperType [a] = ListZipper a
enter = ...
focus = ...
型功能趣味一>是一个很好的介绍键入人们已经熟悉Haskell的代名词家庭。我也写了如何类型的文章同义词家庭往往可以用来代替函数依赖前一阵子。
希望这有助于!
不隶属于 StackOverflow