Haskell:`reverse`或right`cons`,效率更高

Question

自从我前一段时间学习Haskell之后,我不断看到人员reverse列表,只是稍后反过来.使用分隔符拆分字符串的以下函数是一个示例:

splitOn ::Eq a => a -> [a] -> [[a]]
splitOn sep str = s_word str []
   where s_word []     w = [reverse w]
         s_word (c:cs) w = if (c == sep) then reverse w : s_word cs []
                           else s_word cs (c:w)

我认为原因是"缺乏"正确/反向利润运算符,如:

rcons xs x = xs ++ [x]

当然,rcons远远低于cons运算符(:).

但是上面的代码似乎通过使用来引入它自己的低效率reverse.我想知道它是否比以下变体更有效或效率更低:

splitOn' ::Eq a => a -> [a] -> [[a]]
splitOn' sep str = s_word str []
   where s_word []     w = [w]
         s_word (c:cs) w = if (c == sep) then w : s_word cs []
                           else s_word cs (rcons w c)

这两种功能似乎都达到了同样的效果.我认为第二个版本似乎更直观(虽然可能不那么聪明).有这样的陷阱rcons吗？(无限名单,懒惰等)

谢谢.

PS输出:

*Main> splitOn' ',' "a,b,"
["a","b",""]

Answer 1

如果使用"double reverse"来添加单个元素,rcons则可能更有效,因为它只会遍历输入列表一次,而每次reverse完成两次遍历时都会遍历输入列表.

但是,在splitOn'您给出的示例中,reverse每个输出字仅使用一次,因为值以反向形式累积开始.更重要的是,(:)之前会reverse被调用几次.

在您的替代方案中rcons,每个新元素reverse都会对列表进行线性遍历,而一旦结果准备好,只会进行一次线性遍历.