Haskell: 组合函数时强制求值/避免垃圾回收

Question

我正在寻找一种优雅的方式来编写以下代码：

import Data.List
import Data.Maybe

combi = [(x,y) | x <- [2..100], y <- [x..100]]

gsp = group (sort [x*y | (x,y) <- combi])
counts = zip (map head gsp) (map length gsp)

multipleProducts x = (fromJust (lookup x counts)) > 1
possibleComb1 = [(x,y) | (x,y) <- combi, multipleProducts (x*y)]

由于我多次重复使用相同的模式，但基于不同的输入集合而不是 [x*y | (x,y) <- combi]，因此我编写了以下代码。

import Data.List
import Data.Maybe

combi = [(x,y) | x <- [2..100], y <- [x..100]]

onlyOneEl e x = (fromJust (lookup x counts)) == 1
    where gs = group (sort e)
          counts = zip (map head gs) (map length gs)

multipleProducts = not.(onlyOneEl [x*y | (x,y) <- combi])
possibleComb1 = [(x,y) | (x,y) <- combi, multipleProducts (x*y)]

然而，每次调用multipleProducts时，Haskell似乎都会计算gs和count，这需要很长时间，而不是仅在第一次计算，因为e的值始终与multipleProducts相同。有没有更好的避免重新计算的优雅方法？除了使用一个函数预先计算counts并将其存储在本地变量中，然后将其传递给onlyOneEl而不使用where之外？

因为我稍后要基于不同的集合重复使用onlyOneEl，并且我想避免拥有多个counts变量。

我理解这里为什么它不会每个函数计算一次，但是，我没有使用x作为我的最后一个参数，因此无法完全以这种方式执行。

提前感谢！

- Ten

---

我倾向于将其写成onlyOneEl e = \ x -> ... where ...，看看这是否有所帮助。 - Louis Wasserman

你是否启用了优化编译？ - dfeuer

@LouisWasserman 那看起来确实像解决方案，但我不是 Haskell 的专家，你能详细说明一下吗？ :) 启用优化并没有改变任何东西。 - Ten

从优雅的角度来看，Data.List.group 函数有点令人讨厌。我建议使用 Data.List.NonEmpty.group 代替，因为它可以避免你使用部分函数 (Prelude.head) 来检查结果。相比之下，Data.List.NonEmpty.head 是完全安全的。 - dfeuer

此外，在实际代码中不应使用 fromJust。 - dfeuer

@Ten，其实很简单，GHC 只能够内联左侧在愚蠢的语法意义下被充分应用的函数。通过执行 eta 转换，GHC 可能会将 onlyOneEl 的主体移动到 multipleProducts 中。 - jberryman

Answer 1

您可以以更加目标导向的方式重写它。不需要深入涉及数学，只需通过生成数据和过滤就可以以更少的计算量实现相同的效果。

在生成产品时，也将乘数添加到元组中，即

combi n = [((x,y),x*y) | x<-[2..n], y<-[x..n]]

现在你可以根据产品进行排序和分组

multi = filter ((>1) . length) . groupBy ((==) `on` snd) . sortBy (comparing snd) . combi

提取元组的第一个元素，这将是(x,y)对，以便多次给出相同的乘积。

map (map fst) (multi 100)

如果您不关心分组，可以将结果展平，即：

concatMap (map fst) (multi 100)

- karakfa

Answer 2

定义

onlyOneEl e x = fromJust (lookup x counts) == 1
    where gs = group (sort e)
          counts = zip (map head gs) (map length gs)

说“给定e和x，设置gs和counts的计算，并使用它们（懒惰计算的）结果计算表达式fromJust (lookup x counts) == 1。你可以完全等效地编写它为：

onlyOneEl e x =
  let gs = ...
      counts = ...
  in fromJust ...

另一方面，如果您使用lambda表达式将x移到另一侧，则：

onlyOneEl e = \x -> fromJust ...
  where ...

然后你将gs和counts拉入外部作用域。这段代码等价于：

onlyOneEl e =
  let gs = ...
      counts = ...
  in \x -> fromJust ...

因此，在将onlyOneEl应用于单个参数时，gs和counts仅会计算一次。

GHC支持一种名为“完全惰性”的转换，它可以进行这种修改，并在认为这是一个好主意时应用它。显然，GHC在这种情况下做出了错误的判断。

- dfeuer