代数数据类型的Haskell映射函数

Question

我有一个代数数据类型Newb定义如下.现在我想为它编写一个自定义的map函数而不使用递归.另外我有一个foldNewb函数也可以帮助.

 data Newb a = Leaf a | Node [Newb a]


foldNewb:: (a->b)->([b]->b)->Newb a -> b
foldNewb f _ (Leaf a) = f a
foldNewb f1 f2 (Node a) = f2 (map (foldNewb f1 f2) a)


Newbmap :: (a->b)-> Newb a -> Newb b

Newbmap f (Leaf a) = (Leaf (f a))
Newbmap f (Node a) = (Node (foldNewb f concat a))

以上是我尝试实现这个功能.我不能比这更进一步,我不明白我在这里做错了什么.任何帮助,将不胜感激.

Answer 1

tl; dr这是你的功能.但是我建议你继续阅读,看看我是如何想出来的,这样你就可以完成思考过程.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f = foldNewb (Leaf . f) Node

你非常接近,而且你foldNewb正确使用,但你正在过度思考它.

首先,您无法命名功能Newbmap.资本名称保留用于类型.所以我们称之为newbmap.现在,foldNewb已经可以同时处理的案件Leaf和Node,所以我们不应该有模式匹配的newbmap都没有.事实上,你的第一个newbmap案例确实foldNewb无论如何都要做,所以让我们考虑第二种情况.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f (Node a) = (Node (foldNewb f concat a))

我们想要折叠我们的数据结构.特别是,我们希望我们的fold调用完全生成新的数据结构.我们不应该Node在最后明确使用,因为foldNewb我们已经为我们工作了.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f a = foldNewb f concat a

现在在第一种情况下,我们需要一个函数a -> Newb b(因为结果将是类型Newb b).你已经过去了f :: a -> b,这非常接近你想要的.我们只需要用一个函数来组合它b -> Newb b,并且Leaf就是这样做的.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f a = foldNewb (Leaf . f) concat a

对于第二个参数,你想要的[Newb b] -> Newb b,这也很容易完成Node.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f a = foldNewb (Leaf . f) Node a

并且(尽管它没有什么区别),我们可以免费提供最终论证.

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f = foldNewb (Leaf . f) Node

所以有一个工作newbmap功能.现在,至于我如何提出所有这些类型,如果您使用GHC,有一个非常有用的功能称为类型孔,您可以使用它来识别您需要的类型.如果你写的话,那么(在调试你的函数时我就是这么做的)

newbmap :: (a->b)-> Newb a -> Newb b
newbmap f = foldNewb _1 _2

那么你会得到非常具体的GHC信息告诉你_1 :: a -> Newb b和_2 :: [Newb b] -> Newb b.那么您的挑战就是找到具有这些特定类型的函数.而这正是我想出了Leaf . f和Node.