Haskell(长得可怕)回文检查

Question

我正在解决臭名昭著的H-99问题，我正在玩问题#6(找出一个列表是否是回文)。我知道大多数解决方案都能在相当短的列表上运行得相当好。现在我该如何编写一个函数来测试一个非常长的列表是否为回文，例如

let ll = [1..10000000] ++ [10000000, 10000000-1..1] ++ [7]

我(也许是天真地)试着这样测试它:

isPalindrome [] = True
isPalindrome [_] = True
isPalindrome [x,y] = x==y
isPalindrome (x:xs) = isPalindrome [x,last xs] && (isPalindrome $ init xs)

我假设如果isPalindrome [x,last xs]求值为False，则&&的昂贵右侧将不被求值

我分析了上面的内容，结果如下:

Mon Jun 30 18:33 2014 Time and Allocation Profiling Report  (Final)
   h99 +RTS -p -RTS
total time  =        1.29 secs   (1292 ticks @ 1000 us, 1 processor)
total alloc = 2,720,050,200 bytes  (excludes profiling overheads)
COST CENTRE  MODULE  %time %alloc
main         Main     95.6  100.0
isPalindrome Main      4.4    0.0
                                                          individual     inherited
COST CENTRE     MODULE                  no.     entries  %time %alloc   %time %alloc
MAIN            MAIN                     43           0    0.0    0.0   100.0  100.0
 CAF            Main                     85           0    0.0    0.0   100.0  100.0
  main          Main                     86           1   95.6  100.0   100.0  100.0
   isPalindrome Main                     87           2    4.4    0.0     4.4    0.0
 CAF            GHC.Conc.Signal          84           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Encoding          77           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Encoding.Iconv    75           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Handle.FD         68           0    0.0    0.0     0.0    0.0
 CAF            GHC.Show                 63           0    0.0    0.0     0.0    0.0

从中我推断出问题是last xs，这可能需要计算整个xs。如果是这样，有没有解决办法?或者只是[a..b]的实现贪婪?

谢谢。

Answer 1

正如您所猜测的那样，last xs是问题所在-它将花费列表长度的线性时间，并强制立即生成整个列表([a..b]是懒惰的，与Haskell列表一样)。所以你的isPalindrome函数总共将是二次时间。

对于一个简单的实现，我将从xs == reverse xs开始，它具有正确的渐近行为(线性)，但具有相对较高的常数因子，并且在reverse到达列表末尾并开始产生结果时，最终将在内存中拥有列表的两个完整副本。

你可能可以通过查看length，然后在中途将列表分开，或者在单遍中做一些更聪明的事情来改进这种方法。

然而，我认为为了更好的行为，你需要切换数据结构-我会看看像Data.Deque或Data.Sequence这样的东西。

Answer 2

我认为这是last xs，正如你所怀疑的。建议:在做任何递归之前，在中点*处拆分字符串，并反转后半部分。然后每次递归时比较两个字符串的第一个字符。*如果字符串长度为奇数，则两个字符串都应包含中间字符

Answer 3

一堆有趣的回文函数被建议在这个reddit帖子:

天真

palindrome list = reverse list == list

Pointfree

palindrome = liftM2 (==) reverse id

应用

palindrome = (==) <$> reverse <*> id

一元

palindrome = reverse >>= (==)