使用foldTree的Haskell mapTree实现

Question

这段代码来自我已经解决的作业。我仍然想弄清楚我是否可以解决我的初步尝试。

所以我们得到了这个树结构和foldTree函数。

data Tree a = Leaf a
 | Node (Tree a) (Tree a)

foldTree :: (b -> b -> b) -> (a -> b) ->  Tree a -> b
foldTree op f (Leaf x)  = f x
foldTree op f (Node l r) = foldTree op f l `op` foldTree op f r

现在mapTree必须使用foldTree实现。我这样做了。

 mapTree :: (a -> b) -> Tree a -> Tree b
 mapTree' f tree = foldTree Node (Leaf . f) tree

我最初提出的并且仍然没有开始工作的是：

 mapTree :: (a -> b) -> Tree a -> Tree b
 mapTree f tree = foldTree Node transFunc tree 
   where transFunc :: Tree a -> Tree b
         transFunc (Leaf x)    = Leaf (f x)
         transFunc (Node l r)  = Node (transFunc l) (transFunc r)

Answer 1

第二个函数是错误的，因为它的类型：Tree a -> Tree b而foldTree期望它是a -> b，其中a取自Tree a。 b要求mapTree为Tree b，因此foldTree的第三个参数应为a -> Tree b类型。

所以transFunc最简单的固定版本是：

mapTree :: forall a b. (a -> b) -> Tree a -> Tree b
mapTree f tree = foldTree Node transFunc tree 
  where transFunc :: a -> Tree b
        transFunc x = Leaf (f x)

请注意，您需要启用ScopedTypeVariables扩展来编译它。

而那个版本的transFunc相当于你的工作解决方案：(Leaf . f)