Haskell: `reverse` or right `cons`, which is more efficient

Question

Since I learned Haskell some time ago, I keep seeing people reverse lists, just to the reverse them back a moment later. The following function for splitting a string with a delimiter is an example:

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)

I think the reason is the "lack" of a right/reverse cons operator like:

rcons xs x = xs ++ [x]

Of course, rcons is by far less efficient than the cons operator (:).

But the above code seems to introduce its own inefficiency by using reverse. I was wondering whether it is more efficient or less efficient than the following variant:

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)

Both functions seem to achieve the same thing. I think the second version seems more intuitive (though maybe less clever). Are there any pitfalls using rcons like this? (infinite list, laziness etc.)

Thanks.

P.S. output:

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

Answer 1

If "double reverse" is used to just add a single element, rcons is likely to be more efficient because it will only traverse the input list once whereas each reverse will do so once making two traversals in total.

However in the splitOn' example you give, reverse is only being used once per output word, as the value is being accumulated in reversed form to begin with. More importantly, (:) will be used several times before reverse is called.

In your alternative with rcons, there would be a linear traversal of the list for each new element, whereas with reverse there will only be a single linear traversal once the result is ready.