E4 / Bespin

昨天还在闲聊的时候和同事聊到有关于Eclipse IDE in Web的话题，起因似乎关于Flex的能力和可能的应用场景。今天便发现有人已经开始行动，并且有所成果了。

E4/Bespin， 一个基于Mozilla Lab Bespin项目的扩展，已经可以玩玩了。

我尝试着按照E4/Bespin页面上面的说明，安装如同小风吹一样顺畅。

foldl by foldr

RWH上在讲述 functional programming 中的fold的时候举了个例子，说foldl也可以由foldr来实现，具体的代码如下：

foldl :: (a->b->a)->a->[b]->a
foldl f z xs = foldr step id xs z
 where step x g a = g (f  a x)

开始总是没想明白，昨天才恍然大悟，具体的例子如下，

foldl (+) 0 [1,2,3] -->
foldr step id [1,2,3] 0 -->
step 1 (step 2 (step 3 id)) 0 -->
step 2 (step 3 id) (1 + 0) -->
step 3 id ((1+0)+2) -->
id (((1+0)+2)+3)

特此记录一下，也算是脑子没白动。

章节的后面有一个与之相关的练习，用foldr实现takeWhile，倒是一个很好的回顾。先试着用foldl来实现一把，毕竟takeWhile应该从左边开始计算。

takeWhile_foldl :: (a->Bool)->[a]->[a]
takeWhile_foldl p xs = head (foldl step [[]] xs)
                     where step x y | p y = init x ++ [last x ++ [y]]
                                    | otherwise = x ++ [[]]

然后，根据上面给出的foldl的foldr解法得到下面的实现:

takeWhile_foldr :: (a->Bool)->[a]->[a]
takeWhile_foldr p xs = head (foldr step id xs [[]])
                        where step x g a | p x = g (init a ++ [last a ++ [x]])
                                         | otherwise = g (a ++ [[]])
                                       

isSuffixOf in Haskell

isSuffixOf是Haskell中的一个常见的List操作，因此也是Prelude的一员。

isSuffixOf的功效类似于Java中String.contains，只不过由于在Haskell中String就是一个List of Char，因此isSuffixOf可以应用于更广泛的List而非String。

在看RWH的时候，在尝试着使用现有的几个List函数来实现一下isSuffixOf，凭着我已有的知识和习惯，给出了如下的代码：

myisInfixOf :: (Eq a)=>[a]->[a]->Bool
myisInfixOf [] _ = True
myisInfixOf _ [] = False
myisInfixOf x y = let (pre, suf) = break (==(head x)) y
               in if isPrefixOf x suf
                  then True
                  else case suf of
                    [] -> False
                    otherwise -> myisInfixOf x $ tail suf

为了表示和我传统的Imperative编成方式有所区别，我尝试了使用higher-order functions，pattern matching还有递归。然而，当我看到了GHC的标准库中的实现后，还是大吃一惊。可以和Java中的String.indexOf做一下比较。

isInfixOf               :: (Eq a) => [a] -> [a] -> Bool
isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)

这个实现在一个tails序列中，寻找任意(any)一个元素，以needle开始。简洁明了，令人吃惊。最有趣的一个地方便是这个tails序列。它首先得到一个序列的tail，然后依次创建tail的tail。这样any查找才起作用。

从时间性能上考虑，由于都是使用的最单纯的查找算法，上面几种没有多大的区别。从空间性能上考虑，感觉上当然Java的实现消耗最小。然而这种比较的意义有多大，却值得考虑。FP可以看作是相对于Imperative较高级的一种语言，其更关注于what to do，而非how to do。由于Lazy evaluation，这个tails序列并没分配想象中的那么多空间。

PinS和RWH同时入围今年的Jolt

来自LtU，Programming in Scala和Real World Haskell同时入围今年的Jolt的Book technical的最后评选名单。

应该可以说明，越来越多的人开始重视functional programming语言了。

书店

前些日子去淮海路，发现心仪的三联书店关了，那应该还是10月份的时候，取而代之的是不知道那家服装店，或是其他类似的东西。这家三联书店店面不大，因此并没有很多空间放置畅销书，教参，家庭百宝书，美容减肥指南等，因此常常会有惊喜。有一次买到过安东尼 伯尔顿这个"流氓"大厨的书。

今天去龙之梦，发现龙强书屋门口的铁栅卷帘门也合的严严实实。原本安排的一天的计划，第一项就没能实践。龙强书店巨大，充斥了各种书籍，三联没有的它都有，并且有过之而无不及。正因为如此，也常常会有惊喜。其他地方找不到的书，往往躺在某个布满灰尘的角落里。

其他的那些自以为有品位的书店，有个有品位的名字，搞些有品位的活动的那种，反而逛起来毫无乐趣可言。

Haskell is lazy

昨天在做Programming Haskell上面的一道练习，脚踏实地的感受了一下Haskell的lazy evaluation得特性。

题目很简单，给出了一个函数unfold，定义如下

unfold :: (b -> Bool) -> (b -> a) -> (b -> b) -> b -> [a]
unfold p h t x | p x = []
            | otherwise = h x : unfold p h t (t x)

unfold通过一个predicate p 来判x的值，如果为True则返回一个空List，否则的话递归计算unfold p h t (t x)，并且把h x的结果加在这个递归返回序列之前。
也就是说，在通常意义下面，predicate p用来结束递归的那个重要的条件。

要求是使用unfold来实现iterate f，(iterate 返回一个无限序列)。

一个解答是

iterate :: (a->a)->a->[a]
iterate f = unfold nf id f
                 where nf x = False

传统的命令式(imperative)程序员乍一看，便会指出一个显而易见的错误，递归的结束条件永远不为真，因为 nf x = False。然而这个判断，却在Haskell面前不成立，起码在当前的这个情况下，因为lazy的Haskell并不急匆匆的一定要找到递归的终止条件不可，才能完成计算。因为在很多情况下，这并非必要。比如，在GHCi下运行take 8 & iterate (*2) 1，便会得到[1,2,4,8,16,32,64]这样一个序列。 我只需要前8个元素，为什么一定要全计算完呢。

Merge Sort in Scala

Merge Sort is a kind of fast sorting algorithm with O(nlog(n)) order.

Merge sort itself is a recursive algorithm and can be expressed neatly even in an Imperative programming like Java. However pattern matching and high order functions in Scala can make this even interesting.

def mergeSort(list:List[Int]):List[Int] = list match {
 case x::Nil=> List(x)
 case _ =>
   val (a, b) = list.splitAt(list.length /2)
   merge(mergeSort(a), mergeSort(b))     
}

def merge(aList:List[Int], bList:List[Int]):List[Int]= bList match {       
 case Nil => aList
 case _ =>
   aList match {
   case Nil => bList
   case x::xs =>
     if (x < bList.head)
    x::merge(xs, bList)
     else
    bList.head::merge(aList, bList.tail)               
   }   
}