Some links here: http://www.scala-lang.org/old/node/10374
In particular, see https://github.com/scalaz/scalaz/blob/master/core/src/main/scala/scalaz/FingerTree.scala and https://github.com/Sciss/FingerTree
I think you can trust the code in scalaz to be sound. If you want a lighter-weight library, you can examine the source code from Sciss and see what you think.