时间戳

首页 > 解决方案 > 如何将函数应用于树的所有元素？

haskell - 如何将函数应用于树的所有元素？

问题描述

data RoseTree a = RoseNode a [RoseTree a] deriving Show

things :: RoseTree String
things = 
    RoseNode "thing" [
        RoseNode "animal" [
            RoseNode "cat" [], RoseNode "dog" []
        ],

        RoseNode "metal" [
            RoseNode "alloy" [
                RoseNode "steel" [], RoseNode "bronze" []
            ],
            RoseNode "element" [
                RoseNode "gold" [], RoseNode "tin" [], RoseNode "iron" []
            ]
        ],       
    ] 
-- Turns string into all upper case
allCaps :: String -> String
allCaps x = map toUpper x
-- This function uses allCaps as a helper function 
--  to turn the elements in tree into upper case
roseMap :: (a -> b) -> RoseTree a -> RoseTree b
roseMap  f  rtree = case rtree of
    RoseNode a []    ->  allCaps a
    RoseNode a sub   ->  Rose (allCaps a) (map (roseMap f sub)

它接受一个函数，并将其应用于玫瑰树的每个元素。通过将函数映射allCaps到 rosetree 来测试结果things。现在所有元素都应该用大写字母书写。

我不知道如何使用递归来编写这个函数。

标签： haskellrecursiontreemap-function

解决方案

您已经在使用递归。实际上，您roseMap f就其本身而言使用：

roseMap :: (a -> b) -> RoseTree a -> RoseTree b
roseMap f  rtree = case rtree of
    RoseNode a [] -> allCaps a
    RoseNode a sub -> Rose (allCaps a) (map (roseMap f sub))

但是由于以下几个原因，上述方法不起作用：

  1. 你不利用f这里。确实是你写Rose (allCaps a)的，所以你不使用f映射元素；
  2. 不sub应该在括号中传递roseMap f；
  3. 你应该使用RoseNode而不是Rose; 和
  4. 您的第一个案例，您返回allCaps a，而不是RoseNode (allCaps a) [].

没有必要区分没有子节点或有子节点的节点。我们可以将映射定义为：

roseMap :: (a -> b) -> RoseTree a -> RoseTree b
roseMap f (RoseNode a xs) = RoseNode (f a) (map (roseMap f) xs)

所以我们在这里使用f a，并且我们对孩子执行映射。

如果我们然后执行roseMapwith allCapsas 函数，我们会得到：

Prelude Data.Char> roseMap allCaps things
RoseNode "THING" [RoseNode "ANIMAL" [RoseNode "CAT" [],RoseNode "DOG" []],RoseNode "METAL" [RoseNode "ALLOY" [RoseNode "STEEL" [],RoseNode "BRONZE" []],RoseNode "ELEMENT" [RoseNode "GOLD" [],RoseNode "TIN" [],RoseNode "IRON" []]],RoseNode "FRUIT" [RoseNode "APPLE" [RoseNode "GRANNY SMITH" [],RoseNode "PINK LADY" []],RoseNode "BANANA" [],RoseNode "ORANGE" []],RoseNode "ASTRONOMICAL OBJECT" [RoseNode "PLANET" [RoseNode "EARTH" [],RoseNode "MARS" []],RoseNode "STAR" [RoseNode "THE SUN" [],RoseNode "SIRIUS" []],RoseNode "GALAXY" [RoseNode "MILKY WAY" []]]]

我们不需要自己实现映射，我们可以启用DeriveFunctor扩展 [ghc-doc]，让 Haskell 为我们完成工作：

{-# LANGUAGE DeriveFunctor #-}

data RoseTree a = RoseNode a [RoseTree a] deriving (Functor, Show)

我们可以这样称呼它fmap :: Functor f => (a -> b) -> f a -> f b：

Prelude Data.Char> fmap (map toUpper) things
RoseNode "THING" [RoseNode "ANIMAL" [RoseNode "CAT" [],RoseNode "DOG" []],RoseNode "METAL" [RoseNode "ALLOY" [RoseNode "STEEL" [],RoseNode "BRONZE" []],RoseNode "ELEMENT" [RoseNode "GOLD" [],RoseNode "TIN" [],RoseNode "IRON" []]],RoseNode "FRUIT" [RoseNode "APPLE" [RoseNode "GRANNY SMITH" [],RoseNode "PINK LADY" []],RoseNode "BANANA" [],RoseNode "ORANGE" []],RoseNode "ASTRONOMICAL OBJECT" [RoseNode "PLANET" [RoseNode "EARTH" [],RoseNode "MARS" []],RoseNode "STAR" [RoseNode "THE SUN" [],RoseNode "SIRIUS" []],RoseNode "GALAXY" [RoseNode "MILKY WAY" []]]]

推荐阅读