2

findIndexBy順序付け関数によってリストで選択された要素のインデックスを返すを作成しようとしています。この関数は、リストをソートして先頭の要素を返すのと同じですが、サイズ制限なしでリストを処理できるように実装したいと考えています。

findIndexBy :: (Ord a) => (a -> a -> Bool) -> [a] -> Integer
findIndexBy f (x:xs) = findIndexBy' xs x 1 0
  where
    findIndexBy' [] _ _ i = i
    findIndexBy' (x:xs) y xi yi = if f x y
      then findIndexBy' xs x (xi + 1) xi
      else findIndexBy' xs y (xi + 1) yi

この実装でStack space overflowは、次の例のように大きなリストを処理するときに取得します (自明)。

findIndexBy (>) [1..1000000]

この問題を解決するためのより洗練された解決策があるはずであることはわかっています。また、最も慣用的で効率的な解決策を知りたいと思っていますが、関数の何が問題なのかを本当に理解したいと思っています。

私は間違っているかもしれませんが、私の実装はfindIndexBy'端末再帰に基づいていると思うので、コンパイラが末尾呼び出しを最適化しないように見える理由がよくわかりません。

if/then/else が原因である可能性があり、次のことも試してみると、同じエラーが発生する可能性があると思いました。

findIndexBy :: (Ord a) => (a -> a -> Bool) -> [a] -> Integer
findIndexBy f (x:xs) = findIndexBy' xs x 1 0
  where
    findIndexBy' [] _ _ i = i
    findIndexBy' (x:xs) y xi yi = findIndexBy' xs (if f x y then x else y) (xi + 1) (if f x y then xi else yi)

末尾呼び出しの最適化が実行されている (実行されていない) 場所を示すようにコンパイラに依頼する簡単な方法はありますか?

参考までに、以下は私が Clojure で書いた同等の関数で、現在 Haskell に移植しようとしています。

(defn index-of [keep-func, coll]
  (loop [i 0
         a (first coll)
         l (rest coll)
         keep-i i]
    (if (empty? l)
      keep-i
      (let [keep (keep-func a (first l))]
        (recur
          (inc i) (if keep a (first l)) (rest l) (if keep keep-i (inc i)))))))

参考までに、前述の Haskell コードは-O3フラグを使用してコンパイルされています。

[leventovの回答後に編集]

問題は遅延評価に関連しているようです。$!とについてはわかりましseqたが、それらを使用して元のコードを修正する場合のベスト プラクティスは何だろうと思います。

の関数に依存する、より慣用的な実装にまだ興味がありますData.List。

[編集]

最も簡単な修正は、ステートメントyi `seq`の前に最初のスニペットを追加することです。if

4

3 に答える 3

3

強打パターンを追加するとうまくいきました。すなわち

{-# LANGUAGE BangPatterns #-}
findIndexBy :: (Ord a) => (a -> a -> Bool) -> [a] -> Integer
findIndexBy f (x:xs) = findIndexBy' xs x 1 0
  where
    findIndexBy' [] _ _ i = i
    findIndexBy' (x:xs) !y !xi !yi = findIndexBy' xs (if f x y then x else y) (xi + 1) (if f x y then xi else yi)

GHC がコードで何をするかを見るには、次のようにコンパイルします。ghc -O3 -ddump-simpl -dsuppress-all -o tail-rec tail-rec.hs > tail-rec-core.hs

GHC コアを読むを参照してください。

Coreただし、強打パターンがある場合とない場合の出力に大きな違いは見つかりませんでした。

于 2013-09-23T06:19:52.773 に答える
3

  1. コードは戻り値を生成するためにアキュムレータ値を必要とするため、これは遅延が失われるケースです。

  2. アキュムレータが怠惰な場合、最終的に評価する必要がある長いサンクのチェーンが得られます。これが関数をクラッシュさせるものです。アキュムレータを厳密に宣言すると、サンクが取り除かれ、大きなリストで機能します。このような場合は、 を使用するのfoldl'が一般的です。

  3. の違いCore:

前髪なし:

main_findIndexBy' =
  \ ds_dvw ds1_dvx ds2_dvy i_aku ->
    case ds_dvw of _ {
      [] -> i_aku;
      : x_akv xs_akw ->
          ...
          (plusInteger ds2_dvy main4)

前髪あり：

main_findIndexBy' =
  \ ds_dyQ ds1_dyR ds2_dyS i_akE ->
    case ds_dyQ of _ {
      [] -> i_akE;
      : x_akF xs_akG ->
        case ds2_dyS of ds3_Xzb { __DEFAULT ->
        ...
        (plusInteger ds3_Xzb main4)

違いはほんのわずかです。最初のケースでは、元の引数 ds2_dvy を使用してそれに 1 を追加します。2 番目のケースでは、最初に引数の値をパターン一致させます (一致したものを確認することさえありません)。値は ds3_Xzb に入ります。

于 2013-09-23T07:24:03.520 に答える
2

遅延が問題であることに気付いた場合、次に確認することは、コードに実装した一般的なパターンです。リストを繰り返し処理し、リストが空のときに返す中間値を持っているだけのように思えます。これはフォールドです! そして実際、折り畳みの観点から関数を実装できます。

findIndexBy f =
  snd . foldl1' (\x y -> if f x y then x else y) . flip zip [0..]

flip zip [0..]まず、この関数は各要素をリスト内のインデックス ( )とペアにし(element, index)ます。次にfoldl1'(空のリストでクラッシュするフォールドの厳密なバージョン) がリストに沿って実行され、条件を満たすタプルがヤンクされますf。次に、このタプル (この場合) のインデックスsndが返されます。

ここでは厳密な折り畳みを使用したため、GHC の厳密性に関する注釈を追加しなくても問題は解決します。

于 2013-09-23T08:08:17.890 に答える