zipWith在Haskell中树木 [英] zipWith for trees in Haskell

问题描述

我正在使用哈斯克尔表达学院：通过多媒体学习函数式编程来学习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 解决方案：

1. 它与列表中的 zip 类似。 zip [1,2] [1,2,3,4] == [（1,1），（2,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 and zipWith. 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:

1. 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.

2. The undefined is inside the value. This allows for example to have:

   mapTree snd (zipTree x y) == y
   

   whenever x has longer branches. Using Node undefined undefined you have mapTree f (zipTree x y) is always an exception whenever the trees aren't isomorphic (because mapTree will try to evaluate undefined).

这篇关于zipWith在Haskell中树木的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！