1

この定義が与えられた場合、一般化された Haskell ツリーの一般化されたfoldrおよびfoldl関数をどのように記述できますか?

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

Haskellでfoldr関数とfoldl関数がどのように機能するかを理解できたとしても、ツリー用のこの一般化された関数をどのように記述するかはよくわかりません。

編集:私はこのようなことを試しました(コンパイルさえしません):

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

EDIT 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
4

3 に答える 3

2

エラーメッセージの全文:

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]
  • あなたはそれを3番目の引数として使用していますfoldr
  • foldr3 番目の引数が型であることを期待します[c]
  • [c]と[Tree a]はタイプが異なるため、これはエラーです

したがってts、何かの型に処理し[c]、その結果をそれ自体foldrの代わりに渡す必要がありtsます。マップ機能は、開始するのに適した場所です。

于 2011-02-13T21:45:43.110 に答える
0

あなたの宿題にそのような解決策が許されるかどうかはわかりませんが、型クラスの使用が問題ない場合は、次のように書くことができます

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などを定義するため、この定義を使用すると、関数の実装は簡単になります。

于 2011-02-14T09:44:36.100 に答える