5

私は現在、Learn youaHaskellの第6章にいます...つい最近99の質問に取り組み始めました。

3番目の問題は、リストのK番目の要素を見つけることです。takeとを使用して実装しましたzip。

私が抱えている問題は、提供されている代替ソリューションを理解することです。

elementAt''' xs n = head $ foldr ($) xs 
                     $ replicate (n - 1) tail

私は「ほぼそこにいる」のですが、よくわかりません。の定義は知って$いますが..上記のコードの実行順序を教えてください。また、これはさまざまな問題の解決策としてよく使用されますか、これは慣用的なものですか、それとも単に...アクロバティックなものですか？

4

2 に答える 2

7

の定義を拡張するとfoldr

foldr f z (x1:x2:x3:...:[]) = x1 `f` x2 `f` x3 `f`... `f` z

あなたはそれelementAt'''がなるのを見る

elementAt''' xs n = head (tail $ tail $ ... $ tail $ xs)

（注：インデックス付けが0ベースreplicate n tailの場合の代わりになります）。replicate (n-1) tail

したがって、適切な回数に適用tailします。これは、十分に長い場合と同じ結果になりますが、短すぎる場合はエラーが発生し、結果のリストを取得します（短すぎる場合は、後者もエラーを発生させます）。と）。xsdrop (n-1) xsxsheadxsdrop (n-1)

したがって、それが行うことは

  • リストの最初の要素を破棄します
  • 結果のリストの最初の要素を破棄します（n-1合計で）
  • head結果のリストを取得します

また、これはさまざまな問題の解決策としてよく使用されますか、これは慣用的なものですか、それとも単に...アクロバティックなものですか？

この場合、アクロバティックです。はfoldr、sを取得して前面に戻る前に、アプリケーション全体を拡張する必要があるためtail、単純なトラバーサルよりも効率が低くなります。

于 2013-01-25T16:50:37.493 に答える
6

それを2つの主要なステップに分けてください。まず、関数は時間を複製tail (n-1)します。だからあなたは次のようなものになってしまいます

elementAt''' xs n = head $ foldr ($) xs [tail, tail, tail, ..., tail]

これで、リスト上のの定義は次のfoldrように拡張されます

foldr f x [y1, y2, y3, ..., yn] = (y1 `f` (y1 `f` (... (yn `f` x))) ...)

したがって、その折り畳みは次のように拡張されます（で置き換えf、$すべてのysをで置き換えますtail）

foldr ($) xs [tail, tail, tail, ..., tail] 
= (tail $ (tail $ (tail $ ...  (tail xs))) ... )
{- Since $ is right associative anyway -}
= tail $ tail $ tail $ tail $ ... $ tail xs

一緒に作曲するという(n-1)呼びかけがあります。tailテールを取った後n-1 、残りのリストの最初の要素を抽出し、それを返します。

構成をより明確にする別の書き方（私の意見では）は次のようになります

elementAt n = head . (foldr (.) id $ replicate (n-1) tail)
于 2013-01-25T16:49:22.923 に答える