Haskell，终端调用优化和懒惰求值

Question

我正在尝试编写一个 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

通过此实现，我在处理大列表时得到了堆栈空间溢出，如以下示例(简单)所示:

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 函数的惯用实现感兴趣。

[编辑]

最简单的修复是在 if 语句之前的第一个片段中添加 yi `seq`。

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 输出有太大区别。