4

[Integer]Haskellでシーケンスを作成しています。シーケンスの数学的定義は、いくつかの正の整数に対して繰り返されるようになっています。このような状況では、シーケンスを終了して、有限リストの長さを決定したいと考えています。

私の解決策の試みは、最初に数学的シーケンスから無限リストを作成することです。次に、最初の要素が繰り返されるまで、すべての要素のリストをフィルタリングします。結果には、リストの繰り返しの先頭を含めないでください。

ここで 2 つの質問/懸念事項があります。

1) リストの先頭をリストの後半の要素に一致させるにはどうすればよいですか? 2) これは私の問題を解決する効率的な方法ですか? (正確なシーケンスについては、必要に応じて後で追加します。今のところ、一般的なコメントを探しています。)

4

2 に答える 2

10

あなたが説明したアルゴリズムは、次のように簡単に実装できます。

findPeriodic :: Eq a => [a] -> [a]
findPeriodic [] = error "there are no periodic sequences in the empty list"
findPeriodic (x : xs) = x : takeWhile (/= x) xs

それはあなたが説明したことを正確に行います。リストの先頭を取り、その先頭要素がリストに再び表示されるまでリストの一部を収集します。たとえば、次のようになります。

list = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, ...]
findPeriodic list => [1, 2, 3, 4, 5]
于 2012-07-24T17:13:16.583 に答える
2

1,2,3,4,5,3,4,5,3,4, ...最初の要素は、 , whereのようなシーケンスで繰り返されることはありません(a !! i) == (a !! j) ==> (a !! (i+1)) == (a !! (j+1))(コメントに追加したように、質問で求めたものとは異なります)。

これはサイクル検出として知られており、最近、たとえばここで議論されました。

于 2012-07-25T11:31:12.803 に答える