Inserting into a list at a specific location using lenses

Question

I'm trying to perform a manipulation of a nested data structure containing lists of elements. After mucking around with various approaches I finally settled on lenses as the best way to go about doing this. They work perfectly for finding and modifying specific elements of the structure, but so far I'm stumped on how to add new elements.

From what I've read, I can't technically use a Traversal as it violates the Traversal laws to insert a new element into a list, and that's assuming I could even figure out how to do that using a Traversal in the first place (I'm still fairly weak with Haskell, and the type signatures for most things in the lens package make my head spin).

Specifically what I'm trying to accomplish is, find some element in the list of elements that matches a specific selector, and then insert a new element either before, or after the matched element (different argument to the function for either before or after the match). Does Control.Lens already have something that can accomplish what I'm trying to do and my understanding of the type signatures is just too weak to see it? Is there a better way to accomplish what I'm trying to do?

It would be fairly trivial if I was just trying to add a new element either to the beginning or the end of a list, but inserting it somewhere specific in the middle is the difficult part. In some of the pre-lens code I wrote I used a fold to accomplish what I wanted, but it was starting to get gnarly on the more deeply nested parts of the structure (E.G. a fold inside of a fold inside of a fold) so I turned to Control.Lens to try to untangle some of that mess.

Thinkable

Have you considered something like a ziplist instead of a normal list? That would make it real easy to insert an element before or after your focus element. – Duffer

I had considered it, but the way the initial data structure is built would be difficult to convert to a ziplist so I'd probably have to convert it after the fact which means a completely separate type hierarchy just to contain the ziplists. It's either that or I convert from list to ziplist and back every time I need to do an insert, which I could do, but doesn't seem like it's any better than just folding over the entire list in the first place. – Thinkable

Answer 1

Using lens pacakge

If we start with knowing the function id can be used like a lens:

import Control.Lens
> [1,2,3,4] ^. id
[1,2,3,4]

Then we can move on to how the list can be modified:

> [1,2,3,4] & id %~ (99:)
[99,1,2,3,4]

The above allows for insertion at the start of the list. To focus on the latter parts of the list we can use _tail from the Control.Lens.Cons module.

> [1,2,3,4] ^. _tail
[2,3,4]
> [1,2,3,4] & _tail %~ (99:)
[1,99,2,3,4]

Now to generalize this for the nth position

> :{
let
_drop 0 = id
_drop n = _tail . _drop (n - 1)
:}
> [1,2,3,4] ^. _drop 1
[2,3,4]
> [1,2,3,4] & _drop 0 %~ (99:)
[99,1,2,3,4]
> [1,2,3,4] & _drop 1 %~ (99:)
[1,99,2,3,4]

One last step to generalize this over all types with a Cons instance we can use cons or <|.

> [1,2,3,4] & _drop 1 %~ (99<|)
[1,99,2,3,4]
> import Data.Text
> :set -XOverloadedStrings
> ("h there"::Text) & _drop 1 %~ ('i'<|)
"hi there"

Versicolor

Answer 2

I think a simple approach would be break down the problem in:

• A function that is of [a] -> SomeAddtionalData -> [a], which is basically responsible to transform the list into another list using some specific data. This is where you add/remove elements from the list and get a new list
• Use lense to extract the List from some nested data structure, pass that list to above defined function, set the returned list in the nested data structure using lense.

Your last paragraph is the indication about what happens when you try to do too much using a generic abstraction like Lens. These generic abstractions are good for some generic purpose and everything else is specific to your problem and should be designed around plain old functions (at least initially, later on in your project you may find some general pattern across your code base which can be abstracted using type classes etc.).

Justice

I think you missed something with that last paragraph, that's what happened when I wasn't using lenses. The nested nature of the data meant I was walking multiple levels of lists using folds to find the location I wanted to insert the new element at. Using lenses to walk at least the parent lists seems cleaner, although for now it seems like I might be stuck with at least one fold to do the actual insert. – Thinkable

Answer 3

Some comments on your problem:

Answer the Question: There may be a way to do what you want to do. The Lens library is amazingly generic. What there is not is a simple or obvious way to make it happen. I think the it will involve the partsOf combinator but I'm not sure.

Comments on Lenses: The lens library is really cool and can apply to an amazing number of problems. My initial temptation as I am learning the library was to try to fit everything into a Lens access or mutation. What I discovered was that it was better to use the lens library to dig into my complex data structures, but once I had a simple element it was better to use the more traditional functional techniques I already knew rather then stretching the Lens library past it's useful limit.

Advice you didn't ask for: Inserting an element into the middle of a list is a bad idea. Not that it cannot be done but it can end up being an O(n^2) operation. (See also this StackOverflow answer.)Zip lists or some other functional data structure may be a better idea. As a side benefit, some of these structures could be made instance of the At class allowing for insertion and deletion using the partial lens combinators.

Everetteverette