相关疑难解决方法(0)

鉴于该计划:

import Debug.Trace
main = print $ trace "hit" 1 + trace "hit" 1

如果我用ghc -O(7.0.1或更高版本)编译,我得到输出:

hit
2

即GHC使用常见的子表达式消除(CSE)来重写我的程序:

main = print $ let x = trace "hit" 1 in x + x

如果我编译-fno-cse然后我看到hit出现两次.

是否可以通过修改程序来避免CSE？是否有任何子表达式e,我可以保证e + e不会CSE'd？我知道lazy,但找不到任何旨在抑制CSE的东西.

这个问题的背景是cmdargs库,其中CSE打破了库(由于库中的杂质).一种解决方案是要求库的用户指定-fno-cse,但我更喜欢修改库.

显然,这只是我用来理解Haskell的一个例子.我不打算使用冒泡排序进行排序,我也不打算通过二次算法中的列表来优化单个迭代.

当列表已经排序时,我希望停止冒泡排序.我编写了这段代码,bubble返回作为元组中的第二项,布尔状态告诉调用者是否进行了交换:

bubble (x:y:ys)
    | x > y = (y : fst (bubble (x:ys)), True)
    | otherwise = (x : fst (bubble (y:ys)), snd (bubble (y:ys)))
bubble x = (x, False)
bubblesort xs
    | snd (bubble xs) = bubblesort (fst (bubble xs))
    | otherwise = fst (bubble xs)

在我熟悉的语言中,它会非常低效,因为如果没有明确的记忆bubble (y:ys),bubble xs它将被重新计算两次.但鉴于Haskell函数没有副作用,我可以假设编译器会优化重复的调用,使我的代码有效吗？

如果没有,那么编写高效冒泡排序的好方法是什么？

我已经看到了检查列表是否排序的方法:

bubbleSort (x:y:xs) = if sorted thisSort then thisSort else bubbleSort thisSort
    where thisSort = (min x y) : bubbleSort …