Building a sequential list in languages with cons/linked lists

Question

In languages where cons lists are a major datatype, it is very easy to create a list from last to first by prepending items. When doing processing from some input file, however, one is most likely to encounter items in first to last order.

Do languages like these typically recurse?

(define (parse file)
 ...
 (cons datum (parse file)))

Use append operations at each step? Build the list in reverse order and then reverse it?

Is there some canonical design pattern that can solve the problem that input is typically going to be in the reverse order of the way the list is constructed?

Answer 1

One common way to do this efficiently, at least in Haskell, is using a difference list which permit O(1) snoc, which is the inverse of cons (yes, it's a silly name).

An alternative is not using linked lists in favor of a more appropriate data structure, such as finger trees (Data.Seq in Haskell, amortized constant time cons/snoc) or queues (there are persistent queues with constant time operations, both amortized and worst-case).

Answer 2

Yes, languages that favor recursive data types almost always also favor recursive functions, and for this kind of stream processing it is the obvious solution. (Particularly if the language runtime supports tail recursion elimination, which it usually does.) With recursive processing, the list in fact comes out in the right order, so everything is well.

Appending is often comparably expensive and would make a linear problem effectively into a quadratic one, therefore it is usually an anti-pattern in functional programming languages.

• John Cartwright: This was my original assumption, but I got distracted thinking; how does it become tail-recursive if you have to hold the state for each cons until the recursive call returns? I can't think of how to do a (parse file acc) without a (reverse acc) at the end or (as you say) making it quadratic by appending.
• SK-logic: You can rewrite reverse tail-recursively with an additional accumulator argument.
• Giorgio: @SK-logic: Interesting, I will try this out. I normally just call reverse when I am finished (this scans the entire list once more but does not increase the complexity). But I had not thought of a tail recursive reverse.