在Real World Haskell中,有一个标题为"没有数组或哈希表的生命"的部分,作者建议列表和树在函数式编程中是首选,而数组或哈希表可能在命令式程序中使用.
这是有道理的,因为在创建新列表或树时,重用部分(不可变)列表或树要比使用数组更容易.
所以我的问题是:
首先,我是一名Haskell新手.我读过这个: 高度可变域中的不可变功能对象 我的问题几乎相同 - 如何有效地编写状态应该改变的算法.让我们以Dijkstra的算法为例.将找到新路径并更新距离.在传统语言中,这很简单,而在Haskell中,例如我只能想到创建全新的距离,这些距离太慢而且占用内存.是否存在类似于设计模式的情况,其中应该实现具有可变数据结构的算法,并且速度和内存使用是主要问题？
我一直在考虑Haskell - 所以仍然是一个初学者.
我一直在考虑计算列表中项目的频率.在具有可变数据结构的语言中,这通常使用哈希表来解决 - 例如Python中的dict或Java中的HashMap.这种解决方案的复杂性是O(n) - 假设哈希表完全适合内存.
在Haskell中,似乎有两种(主流)选择 - 对数据进行排序然后对其进行分组和计数或使用Data.Map.如果使用排序,它将主导解决方案的运行时,因此复杂度为O(n log n).同样,Data.Map使用平衡树,因此在其中插入n个元素也将具有复杂度O(n log n).
如果我的分析是正确的,那么我认为通过诉诸可变数据结构可以最有效地解决这个特定问题.还有其他类型的问题吗？一般来说,使用Haskell的人会如何处理这样的事情？
Karva表示法用于基因表达式编程以表示数学表达式.
见http://www.gene-expression-programming.com/Tutorial002.asp
您可以通过读取基因并从左到右,从上到下填充节点来创建表达式树.
因此,例如,使用"+*+ 1 + 2*3456"中的运算符(+,*)和终端(1,2,3,4,5,6)将评估为39.
我如何使用attoparsec(或parsec)在haskell中执行此操作？
karvaParser :: Parser Int
karvaParser = ????????????
Prelude> parse karvaParser "+*+1+2*3456"
Done 39