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序列并没分配想象中的那么多空间。

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个元素，为什么一定要全计算完呢。

Real World Haskell

很多人都很兴奋的提到说，受到了从Amazon寄来的Real World Haskell。

...

其实我，好几天前就通过非正规手段 （实在是辜负了大家的期望，很是对不起勤勤恳恳的作者，和辛辛苦苦的pre-reader），得到了chm版本。但是似乎最近还没有时间细读，惭愧惭愧。