因此,对于Haskell中的任何内置类型,我可以构造一个算术序列,就像这个(for Int或Integer等)
[1..5]
但是如果我定义一个枚举类型:
data Suit = Club | Diamond | Heart | Spade deriving (Show, Enum)
当我创建一个算术序列时,我必须在枚举实例和点点之前包含空格,例如
[Club .. Diamond]
为什么？
我的问题是,当使用Haskell中的任何Map实现时,我总是在使用一百万个值时得到"堆栈空间溢出".
我要做的是处理一对配对列表.每一对包含两个Ints(不是整数,我失败了,所以我尝试了Ints).我想浏览列表中的每一对,并使用第一个Int作为键.对于每个唯一键,我想构建第二个元素的列表,其中每个第二个元素都在一对中,具有相同的第一个元素.所以我最终想要的是从Int到Int列表的"Map".这是一个例子.
给出这样的对列表:
[(1,10),(2,11),(1,79),(3,99),(1,42),(3,18)]
我想最终得到一个像这样的"地图":
{1 : [42,79,10], 2 : [11], 3 : [18,99]}
(我在上面使用类似Python的符号来说明"地图".我知道它不是Haskell.它仅用于说明目的.)
所以我尝试的第一件事是我自己手工制作的版本,我在其中排序了Ints对的列表,然后通过列表构建了一个新的对列表,但这次第二个元素是一个列表.第一个元素是键,即每对的第一个元素的唯一Int值,第二个元素是每个原始对的第二个值的列表,其中键作为第一个元素.
所以给出这样的对列表:
[(1,10),(2,11),(1,79),(3,99),(1,42),(3,18)]
我最终得到了一对像这样的对:
[(1, [42,79,10], (2, [11]), (3, [18,99])]
这很容易做到.但是有一个问题.原始列表(1000万对)中"排序"功能的表现令人震惊.我可以在不到一秒的时间内生成原始的对列表.我可以在不到一秒的时间内将已排序的列表处理到我手工制作的地图中.但是,对原始列表对进行排序需要40秒.
所以我想在Haskell中使用其中一个内置的"Map"数据结构来完成这项工作.我的想法是构建我的原始对列表,然后使用标准Map函数构建标准Map.
这就是梨形的地方.它在100,000个值的列表上运行良好但是当我移动到100万个值时,我得到"堆栈空间溢出"错误.
所以这里是一些遭遇问题的示例代码.请注意,这不是我想要实现的实际代码.它只是一个非常简化的代码版本,存在同样的问题.我真的不想将一百万个连续数字分成奇数和偶数分区!!
import Data.IntMap.Strict(IntMap, empty, findWithDefault, insert, size)
power = 6
ns :: [Int]
ns = [1..10^power-1]
mod2 n = if odd n then 1 else 0
mod2Pairs = zip (map mod2 ns) ns
-- Takes a list of pairs and returns a Map where the key is the unique Int values
-- …