Обобщенные foldr и foldl для использования с родовыми деревьями Haskell? - PullRequest
Новая
       60

Обобщенные foldr и foldl для использования с родовыми деревьями Haskell?

1 голос
/ 13 февраля 2011

Как мне написать обобщенную функцию foldr и foldl для общих деревьев Haskell, учитывая это определение? 

data (Eq a, Show a) => Tree a = Void | Node a [Tree a]
    deriving (Eq, Show)

treefoldr :: (Eq a, Show a) => 
   (a -> b -> c) -> c -> (c -> b -> b) -> b -> Tree a -> c

treefoldl :: (Eq a, Show a) =>
   (b -> a -> c) -> c -> (c -> b -> b) -> b -> Tree a -> c

Даже если я могу понять, как работают функции foldr и foldl в Haskell, я не совсем уверен, как написать эту обобщенную функцию для деревьев.

РЕДАКТИРОВАТЬ : я пробовал что-то вроде этого (даже не компилируя): 

treefoldr  _ g1 _ _    Void       = g1
treefoldr f1 g1 f2 g2 (Node a ts) = f1 a (foldr f2 g2 ts)

РЕДАКТИРОВАТЬ 2 : еще одна попытка ... 

treefoldr _ z1 _ _   Void      = z1
treefoldr f z1 g z2 (Node a ts) =
   f a (foldr g z2 (map (\x -> treefoldr f z1 g z2 x) ts))

treefoldl _ z1 _ _   Void      = z1
treefoldl f z1 g z2 (Node a ts) =
   f (foldl g z2 (map (\x -> treefoldl f z1 g z2 x) ts)) a

treefoldr работает, однако treefoldl нет: 

Couldn't match expected type `c' against inferred type `b'
      `c' is a rigid type variable bound by
          the type signature for `treefoldl' at trees.hs:47:42
      `b' is a rigid type variable bound by
          the type signature for `treefoldl' at trees.hs:47:32
    In the first argument of `foldl', namely `g'
    In the first argument of `f', namely
        `(foldl g z2 (map (\ x -> treefoldl f z1 g z2 x) ts))'
    In the expression:
        f (foldl g z2 (map (\ x -> treefoldl f z1 g z2 x) ts)) a

Ответы [ 3 ]

2 голосов
/ 14 февраля 2011

Сообщение об ошибке полностью: 

Couldn't match expected type `c' against inferred type `Tree a'
  `c' is a rigid type variable bound by
      the type signature for `treefoldr' at so.hs:5:14
  Expected type: [c]
  Inferred type: [Tree a]
In the third argument of `foldr', namely `ts'
In the second argument of `f1', namely `(foldr f2 g2 ts)'

Это означает, что

  • ts относится к типу [Tree a]
  • вы используете его в качестве третьего аргумента для foldr
  • foldr ожидает, что его третий аргумент будет иметь тип [c]
  • [c] и [Tree a] - это разные типы, поэтому это ошибка

Так что вам нужно обработать ts во что-то типа [c] и передать этот результат foldr вместо ts. Функция map будет хорошим местом для начала.

0 голосов
/ 04 сентября 2013

Я разговаривал с тем же вашим профессором, в конце концов я нашел правильное решение: 

treefoldr :: (Eq a, Show a) => (a -> b -> c) -> c -> (c -> b -> b) -> b -> Tree a -> c
treefoldr _ z1 _ _   Void      = z1
treefoldr f z1 g z2 (Node a ts) = f a $ foldr (aggr) z2 ts
    where
        aggr t z = g (treefoldr f z1 g z2 t) z

treefoldl :: (Eq a, Show a) => (b -> a -> c) -> c -> (c -> b -> b) -> b -> Tree a -> c
treefoldl _ z1 _ _   Void      = z1
treefoldl f z1 g z2 (Node a ts) = f (foldl (aggr) z2 ts) a
    where
        aggr z t = g (treefoldl f z1 g z2 t) z

С уважением

0 голосов
/ 14 февраля 2011

Я не знаю, разрешено ли такое решение для вашей домашней работы, но когда использование классов типов в порядке, вы можете написать 

import Data.Foldable
import Data.Monoid

data Tree a = Void | Node a [Tree a]
    deriving (Eq, Show)


instance Foldable Tree where 
   foldMap f Void = mempty
   foldMap f (Node value []) = f value
   foldMap f (Node value (x:xs)) = foldMap f x `mappend` foldMap f (Node value xs)

Используя это определение, реализация ваших функций должна бытьтривиально, поскольку Foldable определяет foldl, foldr и т. д.

...