Haskell版本算法比Python3运行慢且内存占用高的原因排查

我在 Codeforces 遇到一道简单问题（题号 1915E），本次讨论聚焦于 Python3 与 Haskell 两种语言的性能差异，而非问题本身。我实现了逻辑一致的函数式风格算法，但 Python3 版本可通过高复杂度测试用例，Haskell 版本却无法通过；同时发现 Haskell 代码的内存占用是 Python3 的 2-8 倍，想了解其中原因。

我近期才开始学习函数式编程，文中可能存在错误。

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()

Haskell 实现代码 #

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 的 2-8 倍，这一点十分可疑

想明确：为何 Haskell 代码运行速度慢于 Python3？是哪些 Haskell 操作导致了性能与内存问题？

更新 #1 #

排查时发现 Haskell 代码中的 let output = foldr (++) "" all_solution，此前误用 foldl 导致代码极慢，改用 foldr 后仍存在问题，这或许有助于故障排查。

内容的提问来源于 stack exchange，提问作者 Khang Truong