Chinaunix首页 | 论坛 | 博客
  • 博客访问: 7304229
  • 博文数量: 159
  • 博客积分: 10424
  • 博客等级: 少将
  • 技术积分: 14605
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-14 12:45
个人简介

啦啦啦~~~

文章分类
文章存档

2015年(5)

2014年(1)

2013年(5)

2012年(10)

2011年(116)

2010年(22)

分类: LINUX

2012-01-15 21:04:51

作者:gfree.wind@gmail.com
博客:blog.focus-linux.net   linuxfocus.blog.chinaunix.net
 
 
本文的copyleft归gfree.wind@gmail.com所有,使用GPL发布,可以自由拷贝,转载。但转载请保持文档的完整性,注明原作者及原链接,严禁用于任何商业用途。
======================================================================================================
前一篇文章中使用haskell实现了快速排序——这个非常符合haskell的特性。下面来看看经典算法二分查找的haskell实现。

注:第一个参数为要查找的目标,第二个参数为排序好的列表。如目标值存在于列表,那么返回true,如果不存在,返回false。

我使用两种方式实现了二分查找
  1. binary_search1' obj [] len = False
  2. binary_search1' obj (x:[]) len = (x == obj)
  3. binary_search1' obj xs len
  4.       | m_value == obj = True
  5.       | m_value > obj = binary_search1' obj (take middle xs) middle
  6.       | m_value < obj = binary_search1' obj (drop (middle+1) xs) (len-middle-1)
  7.       where middle = (len-1) `div` 2
  8.             m_value = xs!!middle

  9. binary_search1 obj xs = binary_search1' obj xs (length xs)
这种方式将已有列表缩短为原来的一半。以C语言的感觉,貌似效率低。但是我感觉haskell不会使用复制的方法来生成新的列表。
简单解释一下,仍然利用haskell函数的pattern match
1. 空列表,返回false
2. 只有一个元素,返回与该元素比较的结果
3. 与中间元素相比较:
    a)如果相等,返回true
    b)  如果中间元素大于目标,那么继续检查中间元素前面的列表
    c)如果中间元素小于目标,那么继续检查中间元素后面的列表


再看另一种方式:
  1. binary_search2' obj [] left right = False
  2. binary_search2' obj xs left right
  3.     | left > right = False
  4.     | m_value == obj = True
  5.     | m_value > obj = binary_search2' obj xs 0 (middle-1)
  6.     | m_value < obj = binary_search2' obj xs (middle+1) right
  7.     where middle = (left+right) `div` 2
  8.           m_value = xs!!middle

  9. binary_search2 obj xs = binary_search2
这种方式与C实现更相似,没有对列表的操作,只是通过移动left和right来实现的。
简单解释一下;
1. 空列表:返回false
2. 非空列表:
a)如果left大于right,返回false
b)如果中间值等于目标,返回true
c)如果中间值大于目标,那么left不变,right变为middle-1
d)如果中间值小于目标,那么right不变,left变为middle+1


haskell的程序写起来果然有不同的感觉,思考问题的方式也与传统的编程语言不同。真的有点意思哦。

阅读(3551) | 评论(2) | 转发(1) |
给主人留下些什么吧!~~

GFree_Wind2012-03-21 16:44:39

TestForCU: 函数数编程。。。在网上找了一下资料。。还是没有看懂~_~..
它的意义在于?它要把变量的值不放到text段内?这样操作起来堆栈就要很大?网上有个这样的例子,
.....
函数式编程,我认为学习的是它的思想,是它为了什么而存在。
可以将其与自己熟悉的语言对比优劣。

TestForCU2012-03-21 14:53:15

函数数编程。。。在网上找了一下资料。。还是没有看懂~_~..
它的意义在于?它要把变量的值不放到text段内?这样操作起来堆栈就要很大?网上有个这样的例子,
int fib(0) {
return 1;
}

int fib(1) {
return 1;
}

int fib(int n) {
return fib(n – 2) + fib(n – 1);

}
这个例子,在哪里能运行?叫C去做不是要改语法么?