Two different implementations for a same functional sequence with O(1) concat and O(n) fromList/toList.

DList.hs

newtype DList a = DList ([a] -> [a])

fromList :: [a] -> DList a
fromList l = DList (l++)

toList :: DList a -> [a]
toList (DList f) = f []

concat :: DList a -> DList a -> DList a
concat (DList lf) (DList rf) = DList $ lf . rf

ListBuilder.hs

data Builder a = Nil | Singleton a | Concat (Builder a) (Builder a)

fromList :: [a] -> Builder a
fromList = foldr (Concat . Singleton) Nil

toList :: Builder a -> [a]
toList = f [] where
    f rest Nil = rest
    f rest (Singleton a) = a:rest
    f rest (Concat l r) = f (f rest r) l