Haskellツリーで整数引数に最も近いキーを見つける

2
Max_ReFactor 2019-12-14 15:44.

命令型言語のバイナリツリーで最も近い下位キーと上位キーを見つける方法はたくさんありますが、Haskellのような純粋に関数型のスタイルでそれを行うための同じ質問はありません。最も近い両方のキーに出会う前に、バイナリセルチツリーを歩き回ることができる方法を知りたいと思います。関数があり、これまでにいくつかのパターンが一致しています。

data TreeMap v = Leaf | Node { pair::(Integer, v), l::TreeMap v, r::TreeMap v} deriving (Show, Read, Eq, Ord)

closestLess :: Integer -> TreeMap v -> (Integer, v)
closestLess i Leaf = error "Tree doesn't include any element"
closestLess i (Node pair tree_r tree_l)
        | i < fst pair = closestLess i tree_l
        | i == fst pair = closestLess i tree_r
        | otherwise = precise i pair tree_r 

この関数を使用して下位キーを取得しますが、整数の引数に最も近いものです。私の意見では、正確にどのような定義が必要か混乱していますが、「正確」のような補助関数を実装する必要があるだけです。私の提案は、その整数値、ノードを「正確な」右側のサブツリーに配置して、ターゲットに最も近いキーを見つけることです。したがって、下のキーと上のキーにもそれを作成する方法について、いくつかのヒントや仮定があります。

1 answers

0

これが私がそれをする方法です:

data TreeMap v = Leaf | Node Integer v (TreeMap v) (TreeMap v) deriving (Show, Read, Eq, Ord)

closestLess :: Integer -> TreeMap v -> Maybe (Integer, v)
closestLess i = precise Nothing where
  precise :: Maybe (Integer, v) -> TreeMap v -> Maybe (Integer, v)
  precise closestSoFar Leaf = closestSoFar
  precise closestSoFar (Node k v l r) = case i `compare` k of
    LT -> precise closestSoFar l
    EQ -> Just (k, v)
    GT -> precise (Just (k, v)) r

これとあなたの試みの違いに関するいくつかの注意:

  • Nodeコンストラクターにレコード構文を使用しました。関数が部分的である(たとえば、pair Leafbottomになる)ため、合計タイプでレコード構文を使用するのは不適切な形式です。実際に使ったことがなく、必要ないので削除しました。
  • キーと値をタプルでラップしましたが、明確な理由はありません。私はそれらを分離し、タイプに直接配置しました。
  • あなたのclosestLess関数は、の戻り値の型を持っていた(Integer, v)、それは常にそのタイプのものを返すことができなかったにもかかわらず、。を使用せずにMaybe (Integer, v)戻ることができるように、に変更しました。(補足:エラーメッセージは技術的に間違っていました。検索値がすべてのノードよりも小さい場所を呼び出すと、ツリーに要素が含まれていても失敗します。)NothingerrorclosestLess
  • あなたのコードは、どちらがノードの左側でどちらが右側のブランチであるかに関して一貫性がありません。私のコードでは、左側のブランチは常にデータコンストラクターの左側にあるブランチです。
  • あなたは別々の警備員で使用i < fst pairi == fst pairました。compare代わりにの出力で大文字と小文字を照合することにより、比較を2回ではなく1回行うだけで済みます。
  • あなたはprecise関数を必要として正しい方向に進んでいましたが、あなたが持っていたロジックの多くはclosestLess実際にその中にある必要がありました。

リンクしたサイトの例を使用した簡単なテストケースを次に示します。

Prelude> tree = Node 9 () (Node 4 () (Node 3 () Leaf Leaf) (Node 6 () (Node 5 () Leaf Leaf) (Node 7 () Leaf Leaf))) (Node 17 () Leaf (Node 22 () (Node 20 () Leaf Leaf) Leaf))
Prelude> closestLess 4 tree
Just (4,())
Prelude> closestLess 18 tree
Just (17,())
Prelude> closestLess 12 tree
Just (9,())
Prelude> closestLess 2 tree
Nothing

Just少し複雑になることを犠牲にして、それをより怠惰にすることもできます(単一の候補が見つかるとすぐにアウターを生成します)。

Data.Functor.Identityをインポートします

データTreeMapv =リーフ| Node Integer v(TreeMap v)(TreeMap v)deriving(Show、Read、Eq、Ord)

closeLess ::整数->ツリーマップv->たぶん(整数、v)
closeLess i =正確ななし
  どこ
    正確::適用t => t(整数、v)->ツリーマップv-> t(整数、v)
    正確なclosestSoFarリーフ= closestSoFar
    正確なclosestSoFar(ノードkvlr)=ケースi `compare` k of
      LT->正確なclosestSoFarl
      EQ->純粋(k、v)
      GT->純粋。runIdentity $正確(Identity(k、v))r

詳細については、これに関する私の質問を参照してください。

Related questions

MORE COOL STUFF

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire が息子の Shelby Blackstock と共有しているクリスマスの伝統について学びましょう。

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルとマライア・キャリーが自然な髪の上でどのように結合したかについて、メーガンの「アーキタイプ」ポッドキャストのエピソードで学びましょう.

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子が家族、特にチャールズ王とウィリアム王子との関係について望んでいると主張したある情報源を発見してください。

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドが、母親のナオミ・ジャッドが亡くなってから初めての感謝祭のお祝いを主催しているときに、彼女が今では家長であることをどのように認識したかを学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

作家のアンバー・ラフィンとジェニー・ヘーゲルが上司のセス・マイヤーズを引き継ぐのを見る

作家のアンバー・ラフィンとジェニー・ヘーゲルが上司のセス・マイヤーズを引き継ぐのを見る

深夜のアンバー・ラフィンとジェニー・ヘーゲルが繰り返し「ジョーク・セス・カント・テル」で戻ってきました。これらのジョークの多くは観客をがっかりさせますが、最初から最後まで素晴らしいです。ルフィンとヘーゲルは黒人女性として自己紹介します。とゲイの女性、それぞれ、したがって、セスマイヤーズが10フィートのポールで触れることができない主題について賢明にクラックすることができます。

ジョンウィック:第3章は2019年5月に劇場への道を容赦なく殺します

ジョンウィック:第3章は2019年5月に劇場への道を容赦なく殺します

(写真:ライオンズゲート)この「キアヌ・リーブスはダッパースーツを着て人々を殺害する」というモチーフ全体が手元にあることをはっきりと知っているライオンズゲートは、スタイリッシュで復讐に燃えるジョン・ウィックのフランチャイズで3回目のリリース日を設定しました。犬をベースにした復讐のためのババ・ヤガの果てしない十字軍を支えるバットシット神話をより深く掘り下げることを約束する3番目のジョン・ウィック映画は、2019年5月17日に設定されました。これまでのところ、それはその日に上陸した唯一の映画です。

このパイロットは、This IsUsの残りの部分に高い基準を設定します

このパイロットは、This IsUsの残りの部分に高い基準を設定します

写真:NBCパイロットは良すぎるのでしょうか?ありそうもないようですが、This IsUsのファンの場合はそうかもしれません。クレイジー、バカ、ラブライターのダン・フォーゲルマンからの待望の新シリーズは、ツイストエンディングを中心に展開しています。シリーズを適切に設定しますが、非常に巧妙に行われているため、改善の余地はあまりありません。

ああ、GIFがついにFacebookで機能する

ああ、GIFがついにFacebookで機能する

ここにいくつかのニュースがあります:あなたは今FacebookにGIFを埋め込むことができます。まあ、技術的には、GIFへのリンクを投稿することができ、Facebookは、他のほとんどすべてのソーシャルネットワークが何年も行ってきたようにアニメーションを作成します。

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

ロシアのフィギュアスケーター、カミラ・バリエバが関与したドーピング事件が整理されているため、チームは2022年北京冬季オリンピックで獲得したメダルを待っています。

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

何千人ものAmazonの買い物客がMulberry Silk Pillowcaseを推奨しており、現在販売中. シルクの枕カバーにはいくつかの色があり、髪を柔らかく肌を透明に保ちます。Amazonで最大46%オフになっている間にシルクの枕カバーを購入してください

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

ラファイエット警察署は、「不審な男性が女性に近づいた」という複数の苦情を受けて、12 月にパデュー大学の教授の捜査を開始しました。

コンセプト ドリフト: AI にとって世界の変化は速すぎる

コンセプト ドリフト: AI にとって世界の変化は速すぎる

私たちの周りの世界と同じように、言語は常に変化しています。以前の時代では、言語の変化は数年または数十年にわたって発生していましたが、現在では数日または数時間で変化する可能性があります。

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

犯罪擁護派のオークランドが暴力犯罪者のロミオ・ロレンゾ・パーハムを釈放

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

認知症を患っている 91 歳のアジア人女性が最近、47 番街のアウター サンセット地区でロメオ ロレンゾ パーハムに襲われました。伝えられるところによると、被害者はサンフランシスコの通りを歩いていたところ、容疑者に近づき、攻撃を受け、暴行を受けました。

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Cómo mejoramos la accesibilidad de nuestro componente de precio, y cómo nos marcó el camino hacia nuevos saberes para nuestro sistema de diseño. Por Ana Calderon y Laura Sarmiento Leer esta historia en inglés.

ℝ

“And a river went out of Eden to water the garden, and from thence it was parted and became into four heads” Genesis 2:10. ? The heart is located in the middle of the thoracic cavity, pointing eastward.

Language