使用Haskell排序函数时堆栈溢出

Question

我在Haskell中实现了一个过滤器,即我可以从命令行调用的程序,如下所示:

$ cat inputfile.txt | myFilter > outputfile.txt

在大约80 MB的文件上运行程序时,我得到堆栈溢出(堆栈空间溢出:当前大小8388608字节.).我在cygwin下使用GHC版本6.12.3.

我认为这个问题来自于sort我在程序中使用的功能,但在我一直在寻找问题三天之后,我不知道如何解决这个问题,所以我想如果有人能给我一个提示.

以下是有关我的计划的重要细节.

我的过滤程序将标准输入读入字符串,将其拆分为行并将每行解析为某种类型的记录 Event

data Event = ...

这是一个实例 Ord

instance Ord Event where
    x < y = ...

这样我就可以使用内置sort函数对事件进行排序.

分割成行并解析事件(每行一个事件)由函数执行

p :: String -> [Event]

内部使用标准功能lines.

我还有一个功能g分组事件:

g :: [Event] -> [[Event]]

g使用了一些与此无关的标准; 每组最多可包含4个事件.

我使用sort(即,每个组内的所有事件进行排序)对每组事件(表示为列表)进行排序,最后使用函数将所有事件组格式化为字符串

f :: [[Event]] -> String

主要功能如下:

main = interact (f . (map sort) . g . p)

如上所述,在大约80 MB的文件上运行此程序会导致堆栈溢出.

如果我用以下函数替换sort函数(一个简单的快速排序实现):

mySort :: [Event] -> [Event]
mySort [] = []
mySort (e:es) = let h = [j | j <- es, j < e]
                    t = [j | j <- es, e < j]
                in
                  (mySort h) ++ [e] ++ (mySort t)


main = interact (f . (map mySort) . g . p)

我没有堆栈溢出!

如果在函数中mySort我用t以下内容替换定义:

                    t = [j | j <- es, e <= j]

即我更换<同<=,堆栈溢出是存在的了!

所以我不清楚这里发生了什么.我看不出我已经引入了任何无限递归.我的另一个假设是,懒惰的评估可以在这里发挥作用(确实<=产生了比<？更大的thunk ).

我有一些Haskell的经验,但我不是真正的专家,所以我很乐意得到一些有用的提示,因为我过去三天一直在努力理解这一点.

Answer 1

罪魁祸首是

instance Ord Event where
    x < y = ...

这是定义Ord实例的错误方法.Ord实例的最小完整定义定义了一个compare或(<=).compare根据(<=)和所有Ord成员函数的默认定义compare.因此,如果你定义(<),那是Ord你可以使用的唯一成员,所有其他成员在被调用时将无限循环,因为他们调用compare,哪些调用(<=),哪些调用compare...

该Data.List.sort函数用于compare确定顺序,因此它在第一次比较时循环.您的自定义快速排序仅使用(<),因此有效.