zipWith在Haskell中树木 [英] zipWith for trees in Haskell
问题描述
使用给出的树的定义
数据树a =节点(树a)(树a)| Leaf a
定义列表函数的树形版本
zip
和zipWith
。在那里
将会出现在树叶或树形状不同的情况下
,您必须做出设计决策。尝试使您的决定
尽可能优雅。
对于 zip
我有这个,但我不确定它是否优雅
zipTree :: Tree a - >树b - >树(a,b)
zipTree(Leaf a)(Leaf b)= Leaf(a,b)
zipTree(Node l1 r1)(Node l2 r2)=
let l = zipTree l1 l2
r = zipTree r1 r2
in Node lr
- 问题...
zipTree(Node _ _)(Leaf _)= Node undefined undefined
zipTree(Leaf _)(Node _ _)= Node undefined undefined
我不确定如何使它适应 zipWith
功能,尽管我确实知道zipWith的一个优雅定义。
zipWith ::(a - > b - > c) - > [a] - > [b] - > [c]
zipWith f(x:xs)(y:ys)= fxy:zipWith f xs ys
zipWith _ _ _ = []
首先我相信你的解决方案并不优雅,因为你使用 undefined
。
您希望尽可能避免部分函数和结构,并在树结构中插入一些 Node undefined undefined
似乎不是一个好主意。
考虑一下:一旦你有一个 Node undefined undefined
它将如何处理其他操作树?你可能会得到很多例外。
所以你必须找到一个替代方案。
zipTree(Node l r)(Leaf a)= Node x y
其中
x = ...?
y = ...?
现在应如何 x
和 y
被定义? x
取决于 l
和 Leaf a
,而 y
应该依赖于 r
和 Leaf a
。
定义这种情况的最简单方法是简单地执行递归调用:
zipTree(Node lr)a @(Leaf _)= Node(zipTree la)(zipTree ra)
因此,我们使用叶节点 l
和 r
子树中的所有叶子> a 。
至于 zipWithTree
:这很简单。你必须添加 f
参数并使用 fxy
来代替(x,y)
当您执行压缩时,仅在 Leaf
v Leaf
情况下完成压缩:
zipWithTree f(Leaf a)(Leaf b)= Leaf $ fab
显然,您必须将 f
参数添加到所有规则中,并将 f
请注意,还有一种其他方式可以定义 zipWith
,即:
zipTree(Node _ _)(Leaf a)= Leaf(undefined,a)
这仍然不是一个好的解决方案,因为它引入了一个 undefined
但是它对 Node有一些优点:节点undefined undefined
解决方案:
-
它与列表中的
zip
类似。zip [1,2] [1,2,3,4] == [(1,1),(2,2)]
-
undefined
是里面的值。这允许例如:
mapTree snd(zipTree xy)== y
只要
x
具有更长的分支。使用节点undefined undefined
您有mapTree f(zipTree xy)
始终是 树不是同构的(因为mapTree
会尝试评估undefined
)。
I am learning Haskell using The Haskell School of Expression: Learning Functional Programming through Multimedia and I am unsure how to go about solving this exercise.
Using the definition of trees given by
data Tree a = Node (Tree a) (Tree a) | Leaf a
Define tree versions of the list functions
zip
andzipWith
. There will be cases at the leaves or where trees are of different shapes where you’ll have to make design decisions. Try to make your decisions as elegant as possible.
For zip
I have this but I am unsure if it is "elegant"
zipTree :: Tree a -> Tree b -> Tree (a,b)
zipTree (Leaf a) (Leaf b) = Leaf (a,b)
zipTree (Node l1 r1) (Node l2 r2) =
let l = zipTree l1 l2
r = zipTree r1 r2
in Node l r
-- Problems...
zipTree (Node _ _) (Leaf _) = Node undefined undefined
zipTree (Leaf _) (Node _ _) = Node undefined undefined
And I am unsure how to adapt it to have zipWith
functionality although I do know a elegant definition of zipWith.
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith _ _ _ = []
First of all I believe your solution is not elegant because you are using undefined
.
You want to avoid partial functions, and structures, as much as possible and simply inserting some Node undefined undefined
in a tree structure doesn't sound like a good idea.
Think about this: once you have a Node undefined undefined
how would it act with the other operations on the tree? You'd probably get tons of exceptions.
So you have to find an alternative.
zipTree (Node l r) (Leaf a) = Node x y
where
x = ... ?
y = ... ?
Now how should x
and y
be defined? x
should depend on l
and Leaf a
while y
should depend on r
and Leaf a
.
The easiest way to define this case is to simply perform the recursive calls:
zipTree (Node l r) a@(Leaf _) = Node (zipTree l a) (zipTree r a)
So we are zipping all leafs in the l
and r
subtrees with the leaf a
.
As for the zipWithTree
: that's easy. You have to add an f
parameter and use f x y
instead of (x, y)
when you perform the zipping, which is done only in the Leaf
v Leaf
case:
zipWithTree f (Leaf a) (Leaf b) = Leaf $ f a b
Obviously you have to add the f
parameter to all the rules and pass f
to recursive calls.
Note that there is also an other way to define zipWith
, which is:
zipTree (Node _ _) (Leaf a) = Leaf (undefined, a)
This still isn't a good solution because it introduces an undefined
however it has some advantages against the Node undefined undefined
solution:
It acts for similarly to
zip
from lists.zip [1,2] [1,2,3,4] == [(1,1), (2,2)]
so you stop when the shorter list ends.The
undefined
is inside the value. This allows for example to have:mapTree snd (zipTree x y) == y
whenever
x
has longer branches. UsingNode undefined undefined
you havemapTree f (zipTree x y)
is always an exception whenever the trees aren't isomorphic (becausemapTree
will try to evaluateundefined
).
这篇关于zipWith在Haskell中树木的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!