Add Traversable instance

[vrom911]

Do you mind to have the Traversable instance for DList?

I am currently using the following custom traverse function:

traverseDList :: (Applicative f) => (a -> f b) -> DList a -> f (DList b)
traverseDList f = fmap DL.fromList . traverse f . DL.toList

I could make a PR if you think that is a desired addition to the library :slightly_smiling_face:

[spl]

Thanks for the suggestion! Unfortunately, I don't think this is a good function to have this in the library.

Generally, to make DList work efficiently for you, you'll want to use it as an intermediate step and not convert to and from a list. That conversion (esp. the fromList, which uses (++)) is inefficient. If you find yourself needing a function with the pattern fromList . f . toList (for some f), you may want to revisit how you're using DList.

See https://github.com/spl/dlist/pull/41#discussion_r429206859 for another recent response of mine to a similar function.

[chshersh]

@spl That's an interesting observation, thanks for the clarification! When looking at the internal implementation of DList, I've noticed that the library already has a few functions that semantically equivalent to fromList . f . toList. For example, the implementation of the Functor instance relies on the following functions:

-- | /O(n)/. Map over difference lists.
map          :: (a -> b) -> DList a -> DList b
map f        = foldr (cons . f) empty

-- | /O(n)/. Foldr over difference lists
foldr        :: (a -> b -> b) -> b -> DList a -> b
foldr f b    = List.foldr f b . toList

In this case, the given DList is deconstructed to list and then created back from the list. Can you elaborate a bit more, how the existing implementation is different from the proposed one for traverse? I'm just curious about the internal implementation details of DList and would like to understand more :slightly_smiling_face:

[spl]

@chshersh Great! I welcome the discussion.

The main goal of difference lists is to avoid left-nested uses of (++), which can lead to super-linear time complexity. The idea is that concatenation (via (++)) is “delayed until the end” of the composition of functions, and that is done with fromList (= DL . (++)).

While the List.foldr in map is used to (re-)construct a DList, it is not applying the (++), which is where the problem lies.

[vrom911]

Thanks @spl and @chshersh for the discussion.

Based on what have been said, I see the following implementation acceptable then:

traverseDList :: (Applicative f) => (a -> f b) -> DList a -> f (DList b)
traverseDList f = foldr (\a fDlistB -> liftA2 DL.cons (f a) fDlistB) (pure DL.empty)

What do you think?

[spl]

@vrom911 At first blush, that looks reasonable. If you want to put together a PR, I'd be happy to take a look at it.