I need to implement a data structure for a finite ordered collection of elements, which needs to support two operations:

- append elements at the end
- fold all elements starting from the beginning

Hence something like this should hold

```
fold (:) "" (append "c" (append "b" (append "a" empty))) = "abc"
```

There are some obvious options:

- Use a simple list: fold is already perfect. Appending at the end is linear in the length of the list, not good
- Use a reversed list: appending at the end (which is actually the start of the list) is perfect, but for folding I need to reserve the list, which is linear in the list length, not good
- I could use
`Seq`

: appending at the end is constant time with`(|>)`

and I have a ready made Foldable instance. But still it allows many more operations and canâ€™t be optimized just for folding.

I know an answer to the question is â€śmeasure in your specific caseâ€ť.

I was just curious whether, theoretically, there is a data structure optimized for such cases