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