Как применить функцию ко всем элементам дерева? - PullRequest
Новая
       18

Как применить функцию ко всем элементам дерева?

4 голосов
/ 07 октября 2019 
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 с розеткой things. Все элементы теперь должны быть написаны в верхнем регистре.

Я понятия не имею, как использовать рекурсию для написания этой функции.

1 Ответ

4 голосов
/ 07 октября 2019

Вы уже используете рекурсию. В самом деле, вы используете roseMap f в терминах самого себя: 

roseMap :: (a -> b) -> RoseTree a -> RoseTree b
<b>roseMap f</b>  rtree = case rtree of
    RoseNode a [] -> allCaps a
    RoseNode a sub -> Rose (allCaps a) (map (<b>roseMap f</b> 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 вместо этого, и мы выполняем сопоставление для дочерних элементов.

Если мы затем выполняем roseMap с allCaps как функция, мы получаем: 

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 <b>DeriveFunctor</b> #-}

data RoseTree a = RoseNode a [RoseTree a] deriving (<b>Functor</b>, 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" []]]]
...