0

私はこの質問をする必要があります：

「二分木と値が与えられると、のルートからリーフへのパスを返す関数findpath:: BTree a -> a -> Path（ aは前の質問のように定義されます）を定義します。プログラムの数は、ツリー内のノード数に比例している必要があります。」BtreetxtxNothing

これまでのところ：

data Maybe a = Nothing | Just a
data BTree a = Leaf a | Fork (BTree a) (BTree a)
type Path = Maybe [Dir]
data Dir = Left | Right

findpath :: Eq a => BTree a -> a -> Path
findpath (Leaf y) x = if y==x then ??? else Nothing
findpath (Fork l r) x = nodepath (findpath l x) (findpath r x) where
   nodepath :: Path -> Path -> Path
   nodepath Nothing Nothing = Nothing
   nodepath Nothing pathr = Just [R]
   nodepath pathl Nothing = Just [L]

私はまだ(Leaf y)ケースの最終的な答えを構築する方法を働かせることができません

4

1 に答える 1

13

あなたの言語は、あなたがプログラムが何をすべきだと思ったかについて、あなたが命令的思考の罠から逃れるために助けが必要であることを私に示唆しています。物事が何をしているのかではなく、物事が何であるかを考えることに基づいて、いくつかの助けを提供しようと思います。

のためfindpath (Leaf y) xに、あなたは正しい方向に向かっています。あなたはただif小文字を与える必要があります、そして正しいものiが何であるかについて考える必要があります。PathLeaf

それでは、他の可能性について考えてみましょう。あなたはそれ以上にそれがいくつかであることを知っていtます。あなたは本当に何を理解しようとしているのか知っています

findpath (Node l r) x

は（=実際、それが何であるか）です。なぜなら、それは。のもう1つの可能性だからBTreeです。BTree「これはa(Leaf y)ですか(Node l r)？」と尋ねて問題を分割することを考えてください。プログラム設計の1つの概念的なステップとして。さて、上記の左側が何に等しいかを理解するために、あなたは再帰的に計算された情報、すなわち何を受け取る権利があります

findpath l x

と

findpath r x

それは。とPathの両方の情報を知っているなら、全体としては何であるかを言うことができますか？Haskellでそれを書くことによってその質問を言い換えさせてください：lrPathNode l r

findpath :: Eq a => BTree a -> a -> Path
findpath (Leaf y)   x = if y==x then ??? else Nothing
findpath (Node l r) x = nodepath (findpath l x) (findpath r x) where
  nodepath :: Path -> Path -> Path
  nodepath ???

再帰的に計算された情報を引数として取るヘルパー関数 を導入することで、私の質問を表現しました。これで、左右のサブツリーの2つのパスにそれぞれパターンマッチングを適用しnodepathて実装を試みることができます。それらがであるかnodepathどうかがわかっている場合は、ノード全体のパスがどうあるべきかを言うことができるはずです。(Just p)Nothing

レッスン1、有用な考えは次の形式です。「これがそのようなものである場合、それはそのようなものでなければなりません。」している、していない。

レッスン2、データ型をプログラミングする基本的な方法は次のとおりです。コンストラクターの場合に分割します（Leaf対Node、Just対Nothing）。再帰呼び出しによってサブ構造から有用な情報を収集します。構造全体の値がどうあるべきかを言います。

私のアドバイスに従って、どうあるnodepathべきかを理解すると、別の名前付き定義であることに値しないほど単純であることがわかるかもしれません。その場合は、nodepath呼び出しをその意味に置き換えて、where-clauseを切り取ります。しかし、それnodepathは問題を解決するための有用な概念的なステップを表現しているので、導入することから始めるのは良いことです。

于 2012-11-11T12:07:38.963 に答える