12

私は 2 つの Haskell 関数を持っていますが、どちらも私と非常に似ているようです。しかし、最初のものは無限リストに対して失敗し、2 つ目は無限リストに対して成功します。その理由を正確に突き止めようと何時間も試みてきましたが、役に立ちませんでした。

どちらのスニペットも、Prelude の「単語」機能を再実装したものです。どちらも有限リストに対してうまく機能します。

無限リストを処理しないバージョンは次のとおりです。

myWords_FailsOnInfiniteList :: String -> [String]
myWords_FailsOnInfiniteList string = foldr step [] (dropWhile charIsSpace string)
   where 
      step space ([]:xs)      | charIsSpace space = []:xs    
      step space (x:xs)       | charIsSpace space = []:x:xs
      step space []           | charIsSpace space = []
      step char (x:xs)                            = (char : x) : xs
      step char []                                = [[char]]

無限リストを処理するバージョンは次のとおりです。

myWords_anotherReader :: String -> [String]
myWords_anotherReader xs = foldr step [""] xs
   where 
      step x result | not . charIsSpace $ x = [x:(head result)]++tail result
                    | otherwise             = []:result

注: 「charIsSpace」は、単に Char.isSpace の名前を変更したものです。

次のインタープリター セッションは、最初のセッションが無限リストに対して失敗し、2 番目のセッションが成功することを示しています。

*Main> take 5 (myWords_FailsOnInfiniteList  (cycle "why "))
*** Exception: stack overflow

*Main> take 5 (myWords_anotherReader (cycle "why "))
["why","why","why","why","why"]

編集：以下の回答のおかげで、私は今理解していると思います。これが私の結論と修正されたコードです。

結論:

  1. 私の最初の試みの最大の原因は、「step space []」と「step char []」で始まる 2 つの方程式でした。ステップ関数の 2 番目のパラメーターを [] に対して一致させることは、2 番目の引数全体を強制的に評価するため、no-noです (ただし、以下で説明する注意事項があります)。
  2. ある時点で、(++) は右辺の引数を cons よりも遅く評価するのではないかと考えていました。そこで、「= (char:x):xs」を「= [char : x] ++ xs」に変更することで問題を解決できるのではないかと考えました。しかし、それは間違っていました。
  3. ある時点で、2 番目の引数を (x:xs) に対してパターン マッチングすると、関数が無限リストに対して失敗するのではないかと考えました。私はこれについてほぼ正しかったが、完全ではない! 上記のパターン マッチで行ったように、(x: xs ) に対して 2 番目の引数を評価すると、何らかの再帰が発生します。「：」（別名、「短所」）に達するまで「クランクを回します」。それが起こらなければ、私の関数は無限リストに対して成功しません。ただし、この特定のケースでは、私の関数は最終的にスペースに遭遇し、その時点で「短所」が発生するため、すべて問題ありません。また、(x:xs) に対するマッチングによってトリガーされる評価は、その場で停止し、無限再帰を回避します。その際、「x」はマッチしますが、xsはサンクのままなので問題ありません。（それを理解するのを本当に助けてくれたGaneshに感謝します）。
  4. 一般に、評価を強制しない限り、2 番目の引数について自由に言及できます。x:xs と照合した場合は、xs の評価を強制しない限り、必要なだけ xs に言及できます。

というわけで、修正後のコードです。私は通常、head と tail を避けようとしますが、それは単にそれらが部分的な関数であるという理由と、同等のパターン マッチングを書く練習が必要だからです。

myWords :: String -> [String]
myWords string = foldr step [""] (dropWhile charIsSpace string)
   where 
      step space acc | charIsSpace space = "":acc
      step char (x:xs)                   = (char:x):xs
      step _ []                          = error "this should be impossible"

これは、無限リストに対して正しく機能します。先頭、末尾、または (++) 演算子が見えないことに注意してください。

さて、重要な注意点として、 最初に修正したコードを書いたとき、「step _ []」に一致する 3 番目の式がありませんでした。その結果、網羅的でないパターン マッチに関する警告を受け取りました。明らかに、その警告を回避することをお勧めします。

しかし、私は問題が発生するだろうと思っていました。2 番目の引数を [] に対してパターン マッチすることは問題ないことは既に述べました。しかし、警告を取り除くためにそうしなければなりません。

しかし、「step_[]」式を追加すると、すべてうまくいきました！無限リストでも問題ありませんでした！. なんで？

修正されたコードの 3 番目の式は決して到達しないためです。

実際、次の BROKEN バージョンを考えてみましょう。空のリストのパターンを他のパターンの上に移動したことを除いて、正しいコードとまったく同じです。

myWords_brokenAgain :: String -> [String]
myWords_brokenAgain string = foldr step [""] (dropWhile charIsSpace string)
   where 
      step _ []                              = error "this should be impossible"
      step space acc | charIsSpace space     = "":acc
      step char (x:xs)                       = (char:x):xs

step が呼び出されたときに最初に発生することは、インタープリターが式 1 が一致するかどうかを確認することであるため、スタック オーバーフローに戻ります。そのためには、2 番目の引数が [] であるかどうかを確認する必要があります。そのためには、2 番目の引数を評価する必要があります。

方程式を他の方程式の下に移動すると、最初または 2 番目のパターンのいずれかが常に一致するため、3 番目の方程式が試行されないことが保証されます。3 番目の式は、網羅的ではないパターン警告を省略するためのものです。

これは素晴らしい学習経験でした。ご協力いただきありがとうございます。

4

4 に答える 4

7

手で式を拡張してみてください。

 take 5 (myWords_FailsOnInfiniteList  (cycle "why "))
 take 5 (foldr step [] (dropWhile charIsSpace (cycle "why ")))
 take 5 (foldr step [] (dropWhile charIsSpace ("why " ++ cycle "why ")))
 take 5 (foldr step [] ("why " ++ cycle "why "))
 take 5 (step 'w' (foldr step [] ("hy " ++ cycle "why ")))
 take 5 (step 'w' (step 'h' (foldr step [] ("y " ++ cycle "why "))))

次の拡張は何ですか？のパターンマッチングを行うにはstep、それが空のリストであるかどうかを知る必要があることがわかります。それを見つけるために、あなたはそれを少なくとも少し評価しなければなりません。しかし、その第2項は、foldrパターンマッチングを行う関数そのものによる削減です。つまり、step関数はそれ自体を呼び出さずに引数を調べることができないため、無限再帰が発生します。

これを2番目の関数の拡張と比較してください。

myWords_anotherReader (cycle "why ")
foldr step [""] (cycle "why ")
foldr step [""] ("why " ++ cycle "why ")
step 'w' (foldr step [""] ("hy " ++ cycle "why ")
let result = foldr step [""] ("hy " ++ cycle "why ") in
    ['w':(head result)] ++ tail result
let result = step 'h' (foldr step [""] ("y " ++ cycle "why ") in
    ['w':(head result)] ++ tail result

スペースに達するまで、この拡張が続くことがおそらくわかります。スペースに達すると、「ヘッド結果」が値を取得し、回答の最初の要素が生成されます。

この2番目の関数は、スペースを含まない無限の文字列に対してオーバーフローするのではないかと思います。理由がわかりますか？

于 2009-05-12T04:52:31.300 に答える
7

他の人は問題を指摘しました。それは、stepが出力を生成する前に常に2番目の引数を評価することですが、2番目の引数は、フォルダーが無限リストに適用されたときのstepの別の呼び出しの結果に最終的に依存します。

このように書く必要はありませんが、2番目のバージョンは、特定の形式を持つステップへの最初の引数に依存しており、ヘッド/テールが決して間違っていないことを確認するのは非常に難しいため、ちょっと醜いです。（私は彼らがそうしないと100％確信していません！）

少なくともいくつかの状況では、入力リストに依存せずに出力を生成するように、最初のバージョンを再構築する必要があります。特に、文字がスペースでない場合、出力リストには常に少なくとも1つの要素があることがわかります。したがって、最初の要素を生成するまで、2番目の引数のパターンマッチングを遅らせます。文字がスペースである場合はリストに依存しますが、スペースの無限のリストを渡す場合にのみケースが無限に繰り返される可能性があるため、これは問題ありません。この場合、出力は生成されず、ループは単語に期待される動作です（他に何ができるでしょうか？）

于 2009-05-12T05:05:11.030 に答える
3

2 番目のバージョンは、独自の回答の一部を生成し始めるresultまで、実際には評価されません。最初のバージョンは、パターン マッチングによってresult すぐに評価されます。

これらの無限リストの鍵は、リスト要素を要求し始める前に何かを作成して、出力が常に入力の「先を行く」ことができるようにする必要があるということです。

（この説明はあまり明確ではないように感じますが、できる限りのことです。）

于 2009-05-12T04:14:20.193 に答える
1

ライブラリ関数foldrには、次の実装（または同様の実装）があります。

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f k (x:xs) = f x (foldr f k xs)
foldr _ k _ = k

の結果はmyWords_FailsOnInfiniteList、結果にfoldr依存stepします。結果は、内部の結果にfoldr依存します。...などに依存します。無限のリストでmyWords_FailsOnInfiniteListは、最初の単語を生成する前に、無限のスペースと時間を消費します。 。

のstep関数は、最初の単語の最初の文字が生成されるまでmyWords_anotherReader、内部の結果を必要としません。foldr残念ながら、Apocalispが言うように、次の単語を生成する前にO（最初の単語の長さ）スペースを使用します。これは、最初の単語が生成されている間、テールサンクが成長し続けるためtail ([...] ++ tail ([...] ++ tail (...)))です。

対照的に、

myWords :: String -> [String]
myWords = myWords' . dropWhile isSpace where
    myWords' [] = []
    myWords' string =
        let (part1, part2) = break isSpace string
        in part1 : myWords part2

次のように定義できるライブラリ関数を使用する

break :: (a -> Bool) -> [a] -> ([a], [a])
break p = span $ not . p

span :: (a -> Bool) -> [a] -> ([a], [a])
span p xs = (takeWhile p xs, dropWhile p xs)

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile p (x:xs) | p x = x : takeWhile p xs
takeWhile _ _ = []

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile p (x:xs) | p x = dropWhile p xs
dropWhile _ xs = xs

中間結果の生成が将来の計算によって妨げられることはなく、結果の各要素が使用可能になるため、O（1）スペースのみが必要であることに注意してください。

補遺

だから、これが改訂されたコードです。私は通常、頭と尾を避けようとします。これは、それらが部分関数であるという理由だけでなく、同等のパターンマッチングを作成する練習が必要なためです。

myWords :: String -> [String]
myWords string = foldr step [""] (dropWhile charIsSpace string)
   where 
      step space acc | charIsSpace space = "":acc
      step char (x:xs)                   = (char:x):xs
      step _ []                          = error "this should be impossible"

（余談ですが、気にしないかもしれませんがwords "" == []、ライブラリからですが、myWords "" = [""]末尾のスペースに関する同様の問題です。）

見た目は大幅に改善されており、ベースのソリューションmyWords_anotherReaderにはかなり適しています。foldr

\n -> tail $ myWords $ replicate n 'a' ++ " b"

O（n）時間よりもうまくいくことはできませんが、両方ともここでO（n）スペースmyWords_anotherReaderを取ります。myWordsを使用すると、これは避けられない場合がありますfoldr。

悪い、

\n -> head $ head $ myWords $ replicate n 'a' ++ " b"

myWords_anotherReaderはO（1）でしたが、パターンマッチングにはさらに結果が必要なため、新しいmyWordsものはO（n）です。(x:xs)

これを回避するには

myWords :: String -> [String]
myWords = foldr step [""] . dropWhile isSpace
   where 
      step space acc | isSpace space = "":acc
      step char ~(x:xs)              = (char:x):xs

は~「反駁できないパターン」を紹介します。反駁できないパターンは決して失敗せず、即時の評価を強制しません。

于 2009-05-12T15:35:43.653 に答える