9

今夜、私はグラフ距離アルゴリズムについて考えていて、車で運転しているときにこれを思いつきました:

module GraphDistance where
import Data.Map

distance :: (Ord a) => a -> Map a [a] -> Map a Int
distance a m = m' 
  where m' = mapWithKey d m
        d a' as = if a == a' then 0 else 1 + minimum (Prelude.map (m'!) as)

とてもエレガントに見えたので、最初はかなり自慢していました。しかし、それがうまくいかないことに気付きました.corecursionがループに陥る可能性があります.

私は自分自身を納得させるためにそれをコーディングしなければなりませんでした：

ghci> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])]
fromList [(0,1),(1,0),(2,^CInterrupted.

でも今思うと、よく考えていたなと思います。

コアカーシブなデータを処理する際の一般的なエラーとアンチパターンのリストを読み進めて、コアカーシブで考えるように脳を訓練できるようにすることはできますか? コアカーシブ以外のデータを考えることについては、経験によってかなりよく訓練されていますが、できれば他の人の間違いから学びたいと思っています。

4

1 に答える 1

13

まあ、コアカーシブデータを扱うときの根本的な間違いは本当に1つだけです。それは、不注意に再帰を使用していることです。

コアカーションは、ある意味でデータが段階的に生成されていることを意味します。グラフ距離関数は、機能するはずなので、ここで参考になります。増分部分をどこに配置するかを考えてください。開始点は、ノードからそれ自体までの距離0です。それ以外の場合は、ノード間の最小距離より1大きい距離です。すぐ隣人。したがって、各距離値は増分であると予想されます。つまり、それら自体が適切にコアカーシブである必要があります。

問題の再帰は、との組み合わせによって発生し(+)ますminimum。最小値を見つけると、何であるかを心配することなく、1常に未満になります...しかし、全体の値を計算せずにsを比較する方法はありません。1 + nnInt

つまり、アルゴリズムは、必要な範囲でのみ(1 +)適用された回数を比較できることを期待しています。0つまり、「ゼロ」と「サクセサ」を使用して定義された怠惰な自然数が必要です。

見よ：

data Nat = Z | S Nat

natToInt :: Nat -> Int
natToInt Z = 0
natToInt (S n) = 1 + natToInt n

instance Show Nat where show = show . natToInt

instance Eq Nat where
    Z == Z = True
    (S n1) == (S n2) = n1 == n2
    _ == _ = False

    Z /= Z = False
    (S n1) /= (S n2) = n1 /= n2
    _ /= _ = True


instance Ord Nat where
    compare Z Z = EQ
    compare Z (S _) = LT
    compare (S _) Z = GT
    compare (S n1) (S n2) = compare n1 n2

そしてGHCiでは：

> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])]
fromList [(0,1),(1,0),(2,1),(3,2)]

アルゴリズムが機能することの証明[0] ; それのあなたの実装はちょうど間違っていました。

ここで、わずかなバリエーションとして、アルゴリズムを別のグラフに適用してみましょう。

> distance 1 $ fromList [(0,[1]),(1,[0]),(2,[3]),(3,[2])]

...これで何ができると思いますか？ノード2または3のノード1からの距離はどれくらいですか？

GHCiで実行すると、明らかな結果が得られます。

fromList [(0,1),(1,0),(2,^CInterrupted.

それにもかかわらず、アルゴリズムはこのグラフで正しく機能します。問題がわかりますか？なぜGHCiにぶら下がったのですか？

要約すると、自由に混合できない2つの形式を明確に区別する必要があります。

  • コアカーシブに生成された、怠惰な、場合によっては無限のデータ
  • 再帰的に消費される有限データ

どちらの形式も、構造にとらわれない方法で変換できます（たとえば、map有限リストと無限リストの両方で機能します）。Codataは、コアカーシブアルゴリズムによって駆動され、段階的に消費できます。データは再帰的に生成できますが、再帰的なアルゴリズムによって制限されます。

できないことは、codataを再帰的に消費するか（たとえば、無限のリストを折りたたむままにする）、またはデータをコアカーシブに生成することです（Haskellでは、怠惰のためにまれです）。

[0]：実際には、一部の入力（たとえば、一部の切断されたグラフ）で失敗しますが、それは別の問題です。

于 2011-06-08T04:05:25.387 に答える