Riffing on jbapple's excellent answer regarding replicate, but using replicateA (which replicate is built on) instead, I came up with the following:
--Unlike fromList, one needs the length explicitly.
myFromList :: Int -> [b] -> Seq b
myFromList l xs = flip evalState xs $ Seq.replicateA l go
where go = do
(y:ys) <- get
put ys
return y
myFromList (in a slightly more efficient version) is already defined and used internally in Data.Sequence for constructing finger trees that are results of sorts.
In general, the intuition for replicateA is simple. replicateA is built on top of the applicativeTree function. applicativeTree takes a piece of a tree of a size m, and produces a well-balanced tree containing n copies of this. The cases for n up to 8 (a single Deep finger) are hard coded. Anything above this, and it invokes itself recursively. The "applicative" element is simply that it interleaves the construction of the tree with threading effects through, such as, in the case of the above code, state.
The go function, which is replicated, is simply an action which gets the current state, pops an element off the top, and replaces the remainder. On each invocation, it thus steps further down the list provided as input.
Some more concrete notes
main = print (length (show (Seq.fromList [1..10000000::Int])))
On some simple tests, this yielded an interesting performance tradeoff. The main function above ran almost 1/3 lower with myFromList than with fromList. On the other hand, myFromList used a constant heap of 2MB, while the standard fromList used up to 926MB. That 926MB arises from needing to hold the entire list in memory at once. Meanwhile, the solution with myFromList is able to consume the structure in a lazy streaming fashion. The issue with speed results from the fact that myFromList must perform roughly twice as many allocations (as a result of the pair construction/destruction of the state monad) as fromList. We can eliminate those allocations by moving to a CPS-transformed state monad, but that results in holding on to far more memory at any given time, because the loss of laziness requires traversing the list in a non-streaming manner.
On the other hand, if rather than forcing the entire sequence with a show, I move to just extracting the head or last element, myFromList immediately presents a bigger win -- extracting the head element is nearly instant, and extracting the last element is 0.8s. Meanwhile, with the standard fromList, extracting either the head or last element costs ~2.3 seconds.
This is all details, and is a consequence of purity and laziness. In a situation with mutation and random access, I would imagine the replicate solution is strictly better.
However, it does raise the question of whether there is a way to rewrite applicativeTree such that myFromList is strictly more efficient. The issue is, I think, that the applicative actions are executed in a different order than the tree is naturally traversed, but I haven't fully worked through how this works, or if there is a way to resolve this.
