算法的 Haskell 复杂度

Question

我在Codeforces上遇到一个简单的问题，问题是this。我想讨论的不是问题，而是我们使用的语言，在本例中是 Python3 和 Haskell。

详细来说，我的算法有两个版本，一个在 Haskell 中，另一个在 Python3 中。两者都采用函数式编程风格。代码看起来像这样

Python3

from operator import add
from itertools import accumulate
from functools import reduce
 
 
def floss(l):
    def e(u):
        a, b = u
        return b if a % 2 == 1 else -b
 
    return map(e, enumerate(l))
 
 
def flock(l):
    return accumulate(l, add)
 
 
def search(l):
    b = zip(l, l[1:])
 
    def equal(u):
        x, y = u
        return x == y
 
    c = any(map(equal, b))
    return 'YES\n' if c else 'NO\n'
 
 
def main():
    t = int(input())
 
    def solution(x):
        return search(sorted(list(flock(floss(x)))))
 
    def get():
        _ = input()
        b = [0] + [int(x) for x in input().split()]
        return b
 
    all_data = [get() for _ in range(t)]
    all_solution = map(solution, all_data)
    print(reduce(add, all_solution))
 
 
main()

哈斯克尔

module Main (main) where
import Data.List (sort)
 
main :: IO ()
main = do
  x <- des
  putStrLn x
 
readInts :: IO [Int]
readInts = fmap (map read.words) getLine
 
flock :: [Int] -> [Int]
flock l = scanr (+) 0 l 
  
floss :: [Int] -> [Int]
floss l = map (e :: (Int, Int) -> Int) $ zip [0..] l where {
  e (u, v) = if mod u 2 == 0 then v else -v
  }
  
search :: [Int] -> String 
search l = if c then "YES\n" else "NO\n" where {
  b = zip l $ tail l;
  c = any (\(x, y) -> x == y) b;
  }
  
solution :: [Int] -> String 
solution = search.sort.flock.floss
 
des :: IO String
des = do 
  io <- readInts
  let t = head io
  all_data <- sequence $ replicate t $ do
    _ <- readInts
    b <- readInts
    return b
  let all_solution = map solution all_data
  let output = foldr (++) "" all_solution
  return output

两者在算法上相对相同。事实上，Python3 通过了高复杂度的测试用例，而 Haskell 代码却不能。我想知道为什么我在 Haskell 中的代码运行速度比 Python3 慢，我想知道 Haskell 的操作导致了错误。我发现可疑的一件事是我的 Haskell 代码的内存使用量比 Python3 代码高得多（2-8 倍）。

我最近才开始学习FP，所以帖子里可能有一些错误。

更新 #1：我发现可能对 bug 检测有用的一件事是 Haskell 代码中是

let output = foldr (++) "" all_solution

。在更糟糕的代码中，我使用了

foldl

而不是

foldr

，这使得代码变得非常慢。我认为这可能会使错误检测任务变得更容易。

Answer 1

我（未经测试）的猜测是使用

scanr

。对于折叠，性能通常允许根据上下文使用

foldr

或

foldl'

，但对于扫描，性能几乎完全需要

scanl

（或其较小的变体，如

scanl1

）。