Learn You A Haskellで Haskell を学習しようとしていますが、焦り、私のお気に入りのアルゴリズムを実装して、できるかどうかを確認したいと思いました。
私はサイクル検出のためのカメ/ウサギのアルゴリズム (フロイドのアルゴリズム) に取り組んでいます。
これまでのコードは次のとおりです。
idx :: (Eq a) => (a -> a) -> a -> a -> a
idx f tortoise hare
| (f tortoise) == (f (f hare)) = (f f hare)
| otherwise = (idx f) (f tortoise) (f f hare)
mu :: (Eq a) => (a -> a) -> a -> a -> Integer -> (Integer, a)
mu f tortoise hare cntr
| (f tortoise) == (f hare) = (cntr+1, f tortoise)
| otherwise = (mu f) (f tortoise) (f hare) (cntr+1)
lam :: (Eq a) => (a -> a) -> a -> a -> Integer -> Integer
lam f tortoise hare cntr
| tortoise == hare = cntr+1
| otherwise = (lam f) tortoise (f hare) (cntr+1)
floyd :: (Eq a) => (a -> a) -> a -> (Integer, Integer)
floyd f x0 =
let z = (idx f) x0 x0
(y1, t) = (mu f) x0 z 0
y2 = (lam f) t (f t) 0
in (y1, y2)
tester :: (Integer a) => a -> a
tester a
| a == 0 = 2
| a == 2 = 6
| a == 6 = 1
| a == 1 = 3
| a == 3 = 6
| a == 4 = 0
| a == 5 = 1
| otherwise = error "Input must be between 0 and 6"
(floyd tester) 0
これは、ロジックを 3 つのステップに分割しようとします。最初に f_idx == f_{2*idx} のインデックスを取得し、最初から移動してパラメーター mu (最初の要素からサイクルの開始までの距離) を取得し、繰り返し (サイクルの長さ) に到達するまで移動します。 .
関数floydは、これらをまとめようとする私のハッキーな試みです。
これが多少機能しないことを除けば、モジュールのロードにも問題があり、理由がわかりません：
Prelude> :load M:\papers\programming\floyds.hs
[1 of 1] Compiling Main ( M:\papers\programming\floyds.hs, interpreted )
M:\papers\programming\floyds.hs:23:12:
`Integer' is applied to too many type arguments
In the type signature for `tester': tester :: Integer a => a -> a
Failed, modules loaded: none.
IntegertoIntまたはの出現箇所をすべて変更しNumても、改善されるわけではありません。
の誤用を理解していませんInt。チュートリアルに従うと、ほとんどの関数の型宣言は常に次の形式になります。
function_name :: (Some_Type a) => <stuff involving a and possibly other types>
しかし、を置き換えると(Eq a)、(Num a)または(Int a)同様のエラーが発生します (タイプが適用された引数が多すぎます)。
これを読んでみましたが、チュートリアルの表記法と一致しません (たとえば、これらの例で定義されているほとんどすべての関数)。
私はタイプとタイプクラスをひどく誤解しているに違いありませんが、それはまさに私が理解したと思ったことであり、上記のコードのように型宣言を行うように導きました。
フォローアップかもしれません: 関数型宣言に複数の TypeClasses を含めるための構文は何ですか? 何かのようなもの：
mu :: (Eq a, Int b) => (a -> a) -> a -> a -> b -> (b, a)
Int（ただし、これにより、適用された引数が多すぎるというコンパイルエラーも発生しました）。
追加した
クリーンアップし、回答に基づいて変更すると、以下のコードが機能しているように見えます。
idx :: (Eq a) => (a -> a) -> a -> a -> a
idx f tortoise hare
| (f tortoise) == (f (f hare)) = (f (f hare))
| otherwise = (idx f) (f tortoise) (f (f hare))
mu :: (Eq a) => (a -> a) -> a -> a -> Integer -> (Integer, a)
mu f tortoise hare cntr
| (f tortoise) == (f hare) = (cntr+1, (f tortoise))
| otherwise = (mu f) (f tortoise) (f hare) (cntr+1)
lam :: (Eq a) => (a -> a) -> a -> a -> Integer -> Integer
lam f tortoise hare cntr
| tortoise == hare = cntr+1
| otherwise = (lam f) tortoise (f hare) (cntr+1)
floyd :: (Eq a) => (a -> a) -> a -> (Integer, Integer)
floyd f x0 =
let z = (idx f) x0 x0
(y1, t) = (mu f) x0 z 0
y2 = (lam f) t (f t) 0
in (y1, y2)
tester :: (Integral a) => a -> a
tester a
| a == 0 = 2
| a == 2 = 6
| a == 6 = 1
| a == 1 = 3
| a == 3 = 6
| a == 4 = 0
| a == 5 = 1
| otherwise = error "Input must be between 0 and 6"
それから私は見る
*Main> floyd tester 2
(1,3)
そして、このテスト関数 (本質的にウィキペディアの例のものと同様) を考えると、これは理にかなっています。a を開始するx0 = 2と、シーケンスは2 -> 6 -> 1 -> 3 -> 6...であり、 mu1 (シーケンスの開始点に到達するには 1 つの要素を移動する必要があります) であり、lam3 (シーケンスは 3 つのエントリごとに繰り返されます) です。
「繰り返す」ことができるようになる前に、最初のポイントを常にバーンインと見なすかどうかについて、いくつかの質問があると思います。
誰かがこれについてアドバイスをくれれば、私は感謝します。特に、私のcntr構造は私には機能していないようです..これは、繰り返される呼び出しの回数をカウントする方法です。変数の状態を保存するのに似ていない、より良い/別の方法があるかどうかはわかりません。