4

有几次我想遍历一个列表并挑选出具有某些属性的元素，这些属性也依赖于列表中的下一个元素。对于一个简单的示例，我有一些代码可以计算函数f在指定的时间间隔内更改符号的次数[a,b]。这在像 C 这样的命令式语言中是相当明显的：

for(double x=a; x<=b; x+=(b-a)/n){
    s*f(x)>0 ? : printf("%e %e\n",x, f(x)), s=sgn(f(x));
    }

在 Haskell 中，我的第一直觉是用它的尾部压缩列表，然后应用过滤器并提取元素fst或其他。但这似乎笨拙且效率低下，所以我硬生生把它变成了一个折叠：

signChanges f a b n = tail $       
    foldl (\(x:xs) y -> if (f x*f y)<0 then y:x:xs else x:xs) [a] [a,a+(b-a)/n..b]

无论哪种方式，我都觉得有一种“正确”的方式来做到这一点（就像在 Haskell 中经常出现的那样），而且我不知道（或者只是没有意识到）它是什么。对于如何以更惯用或更优雅的方式表达这一点的任何帮助，以及关于如何找到“正确”做事方式的建议，将不胜感激。

4

3 回答 3

4

如果您使用 -O2 运行列表融合，则压缩是有效的。在这种情况下不需要使用折叠是 Haskell 的基本优势之一，因为它提高了模块化。

所以拉链是正确的方法。

于 2012-10-07T10:00:36.663 回答
3

这是一个使用超同态的“版本”（与问题不太一样——但它应该足够有用地说明一个超同态），首先我们需要para它，因为它不在标准库中：

-- paramorphism (generalizes fold)
para :: (a -> ([a], b) -> b) -> b -> [a] -> b
para phi b = step
  where step []     = b
        step (x:xs) = phi x (xs, step xs)

使用 paramorphism 很像使用 fold，但除了看到累加器，我们还可以看到输入的其余部分：

countSignChanges :: [Int] -> Int
countSignChanges = para phi 0
  where
    phi x ((y:_),st)  = if signum x /= signum y then st+1 else st
    phi x ([],   st)  = st


demo = countSignChanges [1,2,-3,4,-5,-6]

与拉紧尾巴相比，它的para好处是我们可以尽可能多地查看输入的其余部分。

于 2012-10-07T11:23:28.683 回答
1

如果您需要计算第 i 个元素的值，但取决于列表的第 j 个元素，最好将 list 转换为Array，无论是可变的还是不可变的。

因此，您将能够在折叠或递归调用中基于当前元素的索引进行任意计算。

于 2012-10-07T09:57:25.807 回答