3

リストの隣接する要素とのペアのリストを返すこの単純な関数があります。

adjacents :: [a] -> [(a,a)]
adjacents (x:y:xs) = [(x,y)] ++ adjacents (y:xs)
adjacents (x:xs) = []

を使用して隣接を書き込もうとして問題が発生しましfoldrた。私はいくつかの調査を行いましたが、何も私にヒントを与えていないようです。どのようにそれを行うことができますか？

4

3 に答える 3

6

このようなトリッキーなフォールドは、結果を直接ビルドしようとするのではなく、フォールドに関数をビルドさせることで解決できることがよくあります。

adjacents :: [a] -> [(a, a)]
adjacents xs = foldr f (const []) xs Nothing
  where f curr g (Just prev) = (prev, curr) : g (Just curr)
        f curr g Nothing     = g (Just curr)

ここでの考え方は、結果が前の要素を含むタイプの関数になるようにすること、またはMaybe a -> [(a, a)]リストの先頭にいる場合です。MaybeNothing

ここで何が起こっているのかを詳しく見てみましょう。

  1. 前の要素と現在の要素の両方がある場合は、ペアを作成し、現在の要素を再帰の結果に渡します。これは、リストの末尾を生成する関数です。

    f curr g (Just prev) = (prev, curr) : g (Just curr)

  2. 前の要素がない場合は、現在の要素を次のステップに渡すだけです。

    f curr g Nothing     = g (Just curr)

  3. リストの最後にある基本ケースconst []は、前の要素を無視します。

このようにすることで、結果は元の定義と同じくらい怠惰になります。

> adjacents (1 : 2 : 3 : 4 : undefined)
[(1,2),(2,3),(3,4)*** Exception: Prelude.undefined
于 2012-10-24T20:57:36.573 に答える
2

あなたの関数は1つではなく2つの要素を見るので、フォールドに適しているとは思いません。

この問題の最善の解決策は

adjacents [] = []
adjacents xs = zip xs (tail xs)

ただし、必要に応じて、折り目のトラベスに靴べらを入れることもできます。まず、補助機能。

prependPair :: a -> [(a,a)] -> [(a,a)]
prependPair x [] = [(x,b)]             where b = error "I don't need this value."
prependPair x ((y,z):ys) = ((x,y):(y,z):ys)

adjacents' xs = init $ foldr prependPair [] xs

エラー値のある最後の要素を作成して破棄することで少しだまされたような気がしますが、ちょっと、フォルダはこれを行うのに良い方法ではないとすでに言ったので、このハックは例だと思いますそれは折り目ではありません。

于 2012-10-24T20:55:46.590 に答える
2

unfoldrの代わりに試すこともできますfoldr。

import Data.List
adjacents xs = unfoldr f xs where
  f (x:rest@(y:_)) = Just ((x,y), rest)
  f _ = Nothing
于 2012-10-25T07:39:16.497 に答える