代数数据类型的 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))

我们想折叠我们的数据结构。特别是，我们希望我们的折叠调用能够完全生成新的数据结构。我们不应该需要显式使用 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，那么有一个非常有用的功能叫做type holes，您可以使用它来确定您需要哪种类型。所以(我在调试你的函数时正是这样做的)如果你写

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 .