本周主要在codewars平台上面,练习haskell代码.

目前已经升级到5kyu级别,110点honor.排名在遥远的7k+名次.

打算进一步在上面练习haskell,努力达到proficent级别(2kyu)吧.至少要到competent级别.

代码全部都在这里github

这里就分享下上面的几个有趣的问题.

整数分拆问题

这个问题,可以看到很多的在动态规划的解法.算法的复杂度为O(N^2).

在wiki上面看到一个五边形数定理,可以很好的解决这个问题.

p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ...

其中,上面的1,2,5,7为广义五边形数w(n) = (3 n n +- n) / 2,前面的符号,始终为1,1,-1,-1,1,1

结合上面的五边形的规律,以及记忆化的策略,可以得到较好的结果.

一个小细节,就是可以上面公式所列的,是按照k的降序分布的.而在实际的代码实践中,可以按照升序排列.

这样的话,p(n)是按照从小到大计算得到的,结合记忆化的策略,可以避免递归太深栈溢出的问题.

汉明数的生成

汉明数是一种正规数.
这里的正规数是regular number,不是normal number.

前者是仅包含素因子2,3,5的整数.后者为数字0~9出现的概率相同的实数.

wiki上面有一个非常好的图,可以说明这个问题.我很喜欢,就放在这里了.

这个问题本身挺简单,关键在于优化的生成速度.在codewars平台上,不同语言,对于速度的要求还不是一致的.
导致python版本,这道题目用了比较长时间才过.

记忆化的策略同样是有用的.可以有效的避免重复计算.

python代码的合并排序,其实并不如list(sort(set(lst)))来的粗暴快捷,因为后者肯定是经过C优化的.

RPN逆波兰式

这个本身比较简单的问题,这里提下主要是感叹下相比于5年前,自己使用C++来实现的逆波兰式,毫无疑问haskell的版本简单了许多许多.

这里也有部分是自己的提高吧.

总结

总的来看,haskell的优点

• 提供了大量的库
  很多编程语言在这点上都是做的越来越好了.大量的库,意味着更快的开发速度,更少的细节bug,更易读.
• 静态语言与类型推断
  同时避免了静态语言和动态语言各自的问题.更多的检查来保证程序的正确性
• 函数式与副作用的分离
  至少有更好的错误处理.至少我觉得Maybe比C的错误码要好多了.