在Haskell中进行编程时(特别是在解决Project Euler问题时,其中次优解决方案往往会对CPU或内存需求造成压力)我经常感到困惑,为什么程序的行为方式如此.我看一下配置文件,尝试引入一些严格,选择另一种数据结构,...但主要是它在黑暗中摸索,因为我缺乏良好的直觉.
此外,虽然我知道如何实现Lisp,Prolog和命令式语言,但我不知道实现一种懒惰的语言.我也有点好奇.
因此,我想了解更多关于从程序源到执行模型的整个链.
我想知道的事情:
应用了哪些典型的优化？
当有多个评估候选者时,执行顺序是什么(虽然我知道它是从所需的输出驱动的,但是在首先评估A然后B之后可能仍然存在很大的性能差异,或者首先评估B以检测到您不需要一点都不)
thunk如何代表？
如何使用堆栈和堆？
什么是CAF？(分析表明有时热点在那里,但我没有线索)
什么是表示类型的好方法LoL a,是...的列表列表a？嵌套级别是任意的,但在外部列表的所有元素上是统一的.
我想到的情况是对列表成员应用分组,然后在每个子组上应用下一个分组,依此类推.事先不知道有多少人必须申请.因此:
rGroupBy :: [(a -> a -> Bool)] -> [a] -> [...[a]...]
额外的布朗尼点为类型签名rGroupBy;-)
例:
假设deweyGroup i基于第i个数字对元素进行分组
rGroupBy [deweyGroup 1, deweyGroup 2]
["1.1", "1.2.1", "1.2.2", "2.1", "2.2", "3"]
得到:
[ [ [ "1.1" ], [ "1.2.1", "1.2.2" ] ],
[ [ "2.1" ], [ "2.2" ] ],
[ [ "3" ] ]
]
后记
一天后,我们有4个优秀的互补解决方案.我很满意答案; 谢谢你们.
我有一个嵌套的,相互递归的数据结构,并希望将计算昂贵的值与某些节点相关联.实际上,我想暂时将Pandoc文档中的Blocks链接到该块中出现的单词列表.
我想避免的不吸引人的选择:
扩展Block数据类型,使其包含单词列表,归结为创建一个带有大量(易碎)样板代码的新扩展Pandoc数据类型
将块映射到单词列表; 由于块太复杂而无法有效地用作密钥,因此这是次优的
我正在寻求解决方案的方向是某种覆盖数据结构,其中包括扩展块,但底层数据类型未受影响,因此我仍然可以使用广泛的Pandoc库.但也许这不是哈斯克尔的思维方式......
后脚本2011-06-12:
正如评论所示,我可能高估了Map方法的成本,部分原因是基于错误的假设.确实:"没有什么比明显的事实更具欺骗性了".
无论如何,我接受了hammar的答案,因为它说明了如何创建可扩展的数据类型.
谢谢
我想生成所有自然数以及它们在素因子中的分解,直到达到某个阈值.
我想出了以下功能:
vGenerate :: [a] -- generator set for monoid B* (Kleene star of B)
-> (a, (a -> a -> a)) -- (identity element, generating function)
-> (a -> Bool) -- filter
-> [a] -- B* filtered
vGenerate [] (g0,_) _ = [g0]
vGenerate (e:es) (g0,g) c =
let coEs = vGenerate es (g0,g) c
coE = takeWhile (c) $ iterate (g e) g0
in concatMap (\m -> takeWhile (c) $ map (g m) coE) coEs
gen然后生成所有自然数以及它们的主要因素:
gen threshold …