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回答后编辑]

该问题似乎与惰性评估有关。虽然我发现了$!and seq，但我想知道使用它们修复原始代码时的最佳实践是什么。

我仍然对依赖Data.List.

[编辑]

最简单的解决方法是在语句yi `seq`之​​前添加第一个片段。if

4

3 回答 3

3

  1. 您的代码需要累加器值才能产生返回值，因此这是惰性丢失的情况。

  2. 当累加器是惰性的时，你会得到一长串需要最终评估的 thunk。这就是使您的功能崩溃的原因。将累加器声明为严格的，您就可以摆脱 thunk 并且它适用于大型列表。在这种情况下，使用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。

于 2013-09-23T07:24:03.520 回答
3

添加爆炸模式对我有用。IE

{-# 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 回答
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 回答