I'm trying to do some abstraction in Haskell98 but doen't know how to do it.
我试图在Haskell98中做一些抽象,但不知道该怎么做。
What I want to do is to define a class for types that may be converted into lists.
我想要做的是为可以转换为列表的类型定义一个类。
toList :: a -> [b]
But I don't know how to define a class for this method. I brought up the following three ideas:
但我不知道如何为这个方法定义一个类。我提出了以下三个想法:
class ToList a b where
toList :: a -> [b]
class ToList a where
toList :: a -> [b]
class ToList a where
toList :: a b -> [b]
The first one doesn't work because Haskell98 doesn't allow multiple parameter classes.
第一个不起作用,因为Haskell98不允许多个参数类。
The second one doesn't work because b depends on a and can't be implemented for every b.
第二个不起作用,因为b依赖于a而不能为每个b实现。
The third doesn't work either because I don't know how to instanciate the class with a type where 'b' isn't the last type-parameter.
第三个也不起作用,因为我不知道如何用“b”不是最后一个类型参数的类型实例化类。
data HTree a b = Nil | Node a b (HTree a b) (HTree a b)
toList Nil = []
toList Node x y l r = toList l ++ [(x,y)] ++ toList r
or
toList Nil = []
toList Node x y l r = toList l ++ [x] ++ toList r
How would I do something like that?
我该怎么做呢?
3 个解决方案
#1
9
See also Data.Foldable in the standard library, which provides a toList function for any Foldable instance. Foldable takes a bit of sophistication to instantiate, but it would be good practice. As a bonus, your HTree type is almost exactly the same as the example instance in the documentation.
另请参见标准库中的Data.Foldable,它为任何可折叠实例提供toList函数。可折叠需要一些复杂的实例化,但这将是一个很好的做法。作为奖励,您的HTree类型几乎与文档中的示例实例完全相同。
Additionally, I recommend changing your HTree to:
另外,我建议您将HTree更改为:
data HTree a = Nil | Node a (HTree a) (HTree a)
And then using HTree (a,b) instead of HTree a b. This single-parameter version will be more easily composable with standard types and instances, and it gets more to the point of what is going on since it depends on both parameters in the same way. It is also a Functor, and defining such an instance will make this type really nice to work with.
然后使用HTree(a,b)代替HTree a b。这个单参数版本将更容易与标准类型和实例组合,并且由于它以相同的方式依赖于两个参数,因此它可以更加发展。它也是一个Functor,定义这样一个实例将使这种类型非常好用。
#2
4
I'd recommend Type classes are not as useful as they first seem - if the putative class has just one interface method, consider declaring a function type instead. I came from an OO background too and found I spent far too much time trying to make "class" mean what I thought it meant, when really I should have been using "data".
我建议Type类没有它们看起来那么有用 - 如果推定类只有一个接口方法,请考虑声明一个函数类型。我也来自OO背景,发现我花了太多时间试图让“课堂”意味着我认为的意思,当我真的应该使用“数据”时。
It is much easier just to write your toList' function and then 'lift' it to operate on your data structure. In fact, the acclaimed Yet Another Haskell Tutorial goes through an extensive exercise showing how it's done, and uses a binary tree as the example. The great thing about doing a lift is it distinguishes what is important - the structure of the datatype, not the implementation of toList' - so once the lift is done to perform 'in order traversal of the datatype', you can use the lift to do anything - toList, print, whatever. Supporting toList isn't the important part of the data structure, so it shouldn't be in a class declaration - the important part is how to traverse the data structure.
只需编写toList'功能,然后'提升'它就可以对数据结构进行操作。事实上,备受赞誉的Yet Another Haskell教程经历了一个广泛的练习,展示了它是如何完成的,并使用二叉树作为例子。关于进行提升的好处在于它区分了重要的东西 - 数据类型的结构,而不是toList'的实现 - 所以一旦完成提升以执行'按顺序遍历数据类型',你可以使用电梯来做任何事 - toList,print等等。支持toList不是数据结构的重要部分,因此它不应该在类声明中 - 重要的部分是如何遍历数据结构。
#3
-1
You probably want to choose the last option for class ToList, and make (HTree a) instance of ToList. Then toList has type (HTree a b) -> [b], not for example (HTree a b) -> [(a,b)]. I assume you are thinking a as "key" and b as "value" type.
您可能希望为类ToList选择最后一个选项,并为ToList创建(HTree a)实例。然后ToList具有类型(HTree a b) - > [b],而不是例如(HTree a b) - > [(a,b)]。我假设你认为是“关键”而b是“价值”类型。
class ToList a where
toList :: a b -> [b]
data HTree a b = Nil | Node a b (HTree a b) (HTree a b)
instance ToList (HTree a) where
toList Nil = []
toList (Node x y l r) = toList l ++ [y] ++ toList r
test = toList (Node "a" 1 (Node "b" 2 Nil Nil) Nil)
-- test == [2,1]
#1
9
See also Data.Foldable in the standard library, which provides a toList function for any Foldable instance. Foldable takes a bit of sophistication to instantiate, but it would be good practice. As a bonus, your HTree type is almost exactly the same as the example instance in the documentation.
另请参见标准库中的Data.Foldable,它为任何可折叠实例提供toList函数。可折叠需要一些复杂的实例化,但这将是一个很好的做法。作为奖励,您的HTree类型几乎与文档中的示例实例完全相同。
Additionally, I recommend changing your HTree to:
另外,我建议您将HTree更改为:
data HTree a = Nil | Node a (HTree a) (HTree a)
And then using HTree (a,b) instead of HTree a b. This single-parameter version will be more easily composable with standard types and instances, and it gets more to the point of what is going on since it depends on both parameters in the same way. It is also a Functor, and defining such an instance will make this type really nice to work with.
然后使用HTree(a,b)代替HTree a b。这个单参数版本将更容易与标准类型和实例组合,并且由于它以相同的方式依赖于两个参数,因此它可以更加发展。它也是一个Functor,定义这样一个实例将使这种类型非常好用。
#2
4
I'd recommend Type classes are not as useful as they first seem - if the putative class has just one interface method, consider declaring a function type instead. I came from an OO background too and found I spent far too much time trying to make "class" mean what I thought it meant, when really I should have been using "data".
我建议Type类没有它们看起来那么有用 - 如果推定类只有一个接口方法,请考虑声明一个函数类型。我也来自OO背景,发现我花了太多时间试图让“课堂”意味着我认为的意思,当我真的应该使用“数据”时。
It is much easier just to write your toList' function and then 'lift' it to operate on your data structure. In fact, the acclaimed Yet Another Haskell Tutorial goes through an extensive exercise showing how it's done, and uses a binary tree as the example. The great thing about doing a lift is it distinguishes what is important - the structure of the datatype, not the implementation of toList' - so once the lift is done to perform 'in order traversal of the datatype', you can use the lift to do anything - toList, print, whatever. Supporting toList isn't the important part of the data structure, so it shouldn't be in a class declaration - the important part is how to traverse the data structure.
只需编写toList'功能,然后'提升'它就可以对数据结构进行操作。事实上,备受赞誉的Yet Another Haskell教程经历了一个广泛的练习,展示了它是如何完成的,并使用二叉树作为例子。关于进行提升的好处在于它区分了重要的东西 - 数据类型的结构,而不是toList'的实现 - 所以一旦完成提升以执行'按顺序遍历数据类型',你可以使用电梯来做任何事 - toList,print等等。支持toList不是数据结构的重要部分,因此它不应该在类声明中 - 重要的部分是如何遍历数据结构。
#3
-1
You probably want to choose the last option for class ToList, and make (HTree a) instance of ToList. Then toList has type (HTree a b) -> [b], not for example (HTree a b) -> [(a,b)]. I assume you are thinking a as "key" and b as "value" type.
您可能希望为类ToList选择最后一个选项,并为ToList创建(HTree a)实例。然后ToList具有类型(HTree a b) - > [b],而不是例如(HTree a b) - > [(a,b)]。我假设你认为是“关键”而b是“价值”类型。
class ToList a where
toList :: a b -> [b]
data HTree a b = Nil | Node a b (HTree a b) (HTree a b)
instance ToList (HTree a) where
toList Nil = []
toList (Node x y l r) = toList l ++ [y] ++ toList r
test = toList (Node "a" 1 (Node "b" 2 Nil Nil) Nil)
-- test == [2,1]