Haskell，终端呼叫优化和延迟评估

Question

我试图编写一个findIndexBy，它将返回排序函数在列表中选择的元素的索引。此函数相当于对列表进行排序并返回top元素，但我希望实现它，以便能够不受大小限制地处理列表。

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/附/ and，并且还尝试了以下操作，这会导致相同的错误：

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。

Answer 1

加入爆炸模式对我很有帮助。那就是。

{-# 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。

见Reading GHC Core。

但是，我还没有发现在有和不带Core模式的输出之间有多大的区别。

Answer 2

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，在第二种情况下，它第一种模式匹配参数的值- -甚至不看它与-匹配的是什么，这导致了对它的评估，而值进入了ds3_Xzb。

Answer 3

当您意识到懒惰才是问题时，第二件事就是您在代码中实现的一般模式。在我看来，你似乎真的只是在迭代一个列表，并携带一个中间值，然后在列表为空时返回--这是一个折叠！实际上，您可以根据折叠实现您的功能：

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

首先，该函数将每个元素与(element, index)列表中的索引((element, index))配对。然后，foldl1' (折叠的严格版本，为空列表崩溃)沿着列表运行，并拔出满足您的f的元组。然后返回此元组的索引(本例中为snd)。

因为我们在这里使用了严格的折叠，所以它也可以解决您的问题，而不需要对GHC进行额外的严格注释。