A lesson

    这两天用haskell实现了一个用蚁群算法求解TSP较优解的程序,思想说来其实很简单,模拟很多只蚂蚁在城市间爬来爬去。每只蚂蚁经过一个城市就在城市上留下一点点气味,由于蚂蚁沿着短的环路跑一圈时间短,于是在一定的时间里,跑过的蚂蚁更多,留下的气味更重,于是又吸引更多的蚂蚁。套句古话:走的蚂蚁多了,也就成了路。
    这道题目原本是我一个朋友的毕业设计,我一共拿到了matlab和c的两个版本,c版本的程序写的很漂亮(看了这段程序后,我突然觉得c其实很KISS,扯远了)。于是我仿照c版本写了一个haskell版本,写的很别扭,脑子打了无数个结,有缠作一团,花了一天终于勉强的写出来了。写着写着我差点向弃Haskell另奔OCaml或者F#又或者Lisp之流,但奇怪的时候,写完之后我看看我的代码觉得很漂亮大笑,又打算继续坚守神奇的Haskell~~
    写完这段程序给我留下的最大印象大致有一下若干:

  • 如何表达循环,fp(相对的一下用ip表示传统的编程模式)中没有所谓的循环,一般寻找递归的解法。回头细细想想,ip方式强调步骤,某个结果可以通过步骤1、步骤2、步骤3……得到,描述出来一切搞定;fp方式强调数据,你把一堆数据作为输入,代入一个表达式,捣鼓捣鼓,哈哈,然后结果出来了,期间步骤是怎么样的,不需要知道。但是由于时间是我们生活的本质,我们更习惯描述步骤,这就带来了fp编程时候的极大不适应。但是抽象的威力是巨大的,步骤也可以被抽象成为数据,步骤与步骤之间的关系也可以描述出来,于是某个大牛在haskell中引入了Monad。一切清净了很多。
  • 全局变量的问题:引入若干个全局使用的东西是很方便的,但是haskell的pure哲学不允许它。于是伟大的抽象有发挥了作用,使用StateMonad可以做相同的事情,基于一下几个原因,还是很不自然的使用:第一,必须设计好用全局变量。第二,获取全局变量不方便。第三,修改全局变量也不方便。第一个原因自然不是坏处,那是理所当然的要求,我是它在写法上很不自然。
  • 效率的问题。函数在haskell中是一等公民(first-class),函数就是数据。于是我突发奇想,所谓的map不就是一个函数,与其像在ip中那样特意去设计一个数据结构来描述,不如就用一个函数吧。想法的确很好很漂亮,于是我在引申一下,用函数来描述矩阵。这个想法同样很好,但是有一个缺点是它不能做Bound Safe Check。当然这完全不妨碍我试一试这个想法。于是在这个程序当中,我用这个方法来存储所有城市间的距离(distance table)和蚂蚁分泌物浓度(pheromone table),第一张表是不变的,而第二张表在迭代过程当中不停的update。于是乎我发现了这个方法的一个致命缺点:效率。比起使用mutable table,效率差了好几倍。
此条目发表在FP分类目录。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 登出 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 登出 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 登出 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 登出 /  更改 )

Connecting to %s