代码之家 › 专栏 › 技术社区 › J.Ober

使用foldtree实现haskell映射树

typeerror tree haskell dictionary

0

J.Ober · 技术社区 · 7 年前

这段代码来自我已经解决的作业。不过,我还是想弄清楚我是否能弥补我最初的尝试。

所以我们得到了这个树结构和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

现在必须使用foldtree实现maptree。我是这样做的。

 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)

0 回复 | 直到 7 年前

1

2

Karol Samborski 7 年前

第二个函数是错误的,因为它的类型: Tree a -> Tree b 虽然 foldTree 希望是 a -> b 在哪里? a 是从 Tree a 是的。 b 是 mapTree 成为 Tree b 因此第三个论点 折叠树 应该是类型 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 编译它的扩展。

还有那个版本的 变形 相当于你的工作方案: (Leaf . f)