任意分支数树上的HaskellMap

gr8qqesn 于 2023-01-21 发布在其他

关注(0)|答案(1)|浏览(106)

我正在尝试为数据类型编写函数mapTree :: (a -> b) -> Tree a -> Tree b

data Tree a = Empty | Node a [Tree a] deriving Show

我知道如果树只有2个（或任意数量）可能的分支，该怎么做，但我有点卡住了，目前为止我的代码如下：

mapTree :: (a -> b) -> Tree a -> Tree b
mapTree _ Empty = Empty
mapTree f (Node a []) = Node (f a) []
mapTree f (Node a (t:ts)) = Node (f a) (mapTree f t : mapTree f ts)

但是mapTree f ts是不允许的，因为ts的类型是[Tree a]。有没有什么办法可以重写它，这样我就不会被这个错误卡住了？

haskell

来源：https://stackoverflow.com/questions/75154410/haskell-map-on-trees-with-any-number-of-branches

1条答案

按热度按时间

6yt4nkrj1#

将长度为k的每个列表视为单独的情况：

mapTree _ Empty = Empty
mapTree f (Node a []) = Node (f a) []
mapTree f (Node a [x]) = Node (f a) [mapTree f x]
mapTree f (Node a [x,y]) = Node (f a) [mapTree f x, mapTree f y]
mapTree f (Node a [x,y,z]) = Node (f a) [mapTree f x, mapTree f y, mapTree f z]
...

看看这表情

[mapTree f x, mapTree f y, mapTree f z, ...]

您可以使用 map 简化此操作，其中Map的函数为mapTree f：

[mapTree f x, mapTree f y, mapTree f z, ...]
    == map (mapTree f) [x, y, z, ...]

它允许您用单个case替换无限数量的固定长度case

mapTree f (Node a xs) = Node (f a) (map (mapTree f) xs)

赞(0）回复(0）举报 2023-01-21

我来回答

任意分支数树上的HaskellMap

1条答案

相关问题

热门标签

最新问答