次のように定義された検索ツリーがあります。
data (Ord a) => Stree a = Null | Fork (Stree a) a (Stree a) deriving Show
mapStree という 2 つの関数を定義する必要があります。
mapStree :: (Ord b, Ord a) => (a -> b) -> Stree a -> Stree b
とfoldStree：
foldStree :: (Ord a) => (b -> a -> b -> b) -> b -> Stree a -> b
何が起こっているのか完全には理解できず、これを行う方法もわかりません。
マップで、ツリーが持つ任意のラベルに関数を適用する必要があります。これは、変換関数として与えられた関数を使用してa、 の出現が の出現に変更されることを意味します。b
これを行うには、Stree. さて、Null簡単です-そもそも依存しませんa。トリッキーなのは、何をするかですFork。にForkは が 1 つaあり、さらに 2 つあるため、 をStree取得する関数と を取得する関数が必要です。前者の場合、 の呼び出しは関数を提供し、後者の場合は、必要な呼び出し署名を (部分的な適用によって!) 持っています。a -> bStree a -> Stree bmapStreemapStree f
の場合foldStree、いくつかの蓄積タイプbと labeltype 、および type の 2 つの値と typeの値を取り、を生成aする蓄積関数があります。これは役に立ちますが、少なくともその累積関数は、ツリー内の任意の場所にある可能性があるものを反映しているためです。再帰により、 left と right の両方から結果があると想定でき、それらを値と組み合わせるだけです。途中で、再帰を渡すための新しい値を与えます。パラメーター toは、各リーフの値を取得することですべてを開始するのに十分な標準値を提供します。babForkStreeabbfoldStree
したがって、foldStree可能なコンストラクターで定義する必要もあります。値のパラメーターを選択し、Null値の場合、パラメーター結合関数ですべてを結合する前Forkに、両方の値に再帰する必要があります。Stree
これが問題に対処するのに十分役立つかどうかをコメントで明確にしてください。
このコースの講義 5 を強くお勧めします。