python - Haskell 极慢的简单递归

Question

我正在试验 Haskell 使用简单的递归 max 算法进行分析:

max_tag :: Integer -> [Integer] -> Integer
max_tag head [] = head
max_tag head (x:xs) =
    let {m = max_tag x xs} in
      let {b = (Prelude.<=) m head} in
        case b of {True -> head; False -> m}

当我将它与 python 命令式等价物进行比较时，我得到了 10 倍的速度因子 以支持 python:

with open("input.txt") as fl:
    data = [int(d) for d in fl.read().splitlines()]
max_ = 0
for d in data:
    if max_ < d:
        max_ = d
print(max_)

• 在 Haskell 的情况下使用尾递归似乎有一个固有的限制，我说的对吗？
• 有什么其他方法可以使 Haskell 代码更快？
• 输入文件包含 1M 个无符号无界整数(平均 32 位)

为了完整性，这里是完整的 Haskell 文件(不确定是否需要):

import Max
import System.IO  
import Control.Monad
import System.Environment
import Prelude

readInt :: String -> Integer
readInt = read

max_tag :: Integer -> [Integer] -> Integer
max_tag head [] = head
max_tag head (x:xs) =
    let {m = max_tag x xs} in
      let {b = (Prelude.<=) m head} in
        case b of {True -> head; False -> m}

main = do
    args <- getArgs
    contents <- readFile "input.txt"
    let numbers_as_strings = words $ contents
    let numbers = map readInt numbers_as_strings
    let max_number = max_tag 0 numbers
    print max_number

编辑:@Willem Van Onsem 建议的重构，有效! (28 秒 -> 12 秒)

max_bar :: Integer -> [Integer] -> Integer
max_bar head [] = head
max_bar head (x:xs) =
  let {b = head < x} in
    let {m = case b of {True -> x; False -> head}} in
      max_bar m xs

关于进一步改进的任何想法？我一定比 python 快!

Answer 1

比@Noughtmare 的答案更有效的方法是使用 Data.ByteString ，它没有处理编码的开销，这里不需要。在我的测试中，以一百万个随机的 32 位数字作为输入，它的运行时间约为 290 毫秒，而@Noughtmare 的答案运行时间约为 1020 毫秒。相比之下，原始的 Python 运行时间约为 560 毫秒。

import qualified Data.ByteString as B
import qualified Data.ByteString.Char8 as C
import Data.Maybe (fromJust)

-- NOTE: This will throw an error if parsing fails.
readInt :: B.ByteString -> Integer
readInt = fst . fromJust . C.readInteger

main :: IO ()
main = do
  contents <- B.readFile "read-integers.txt"
  let numbers = map readInt $ C.lines contents
  print $ max_tag 0 numbers

max_tag :: Integer -> [Integer] -> Integer
max_tag head [] = head
max_tag head (x : xs) = max_tag (max head x) xs