Вставка в список в определенном месте с помощью линз

Я пытаюсь выполнить манипулирование вложенной структурой данных, содержащей списки элементов. После осмотра разных подходов я наконец-то остановился на линзах как на лучшем способе сделать это. Они отлично работают для поиска и изменения определенных элементов структуры, но пока я не знаю, как добавлять новые элементы.

Из того, что я прочитал, я не могу технически использовать Обход, поскольку он нарушает законы Обхода, чтобы вставить новый элемент в список, и это предполагает, что я мог бы даже выяснить, как это сделать, используя Обход в первую очередь (Я все еще довольно слаб с Haskell, и подписи типов для большинства вещей в пакете линз заставляют мою голову вращаться).

Конкретно, что я пытаюсь сделать, это найти какой-то элемент в списке элементов, который соответствует определенному селектору, а затем вставить новый элемент либо до, либо после сопоставленного элемента (другой аргумент функции для до или после матч). У Control.Lens уже есть что-то, что может выполнить то, что я пытаюсь сделать, и мое понимание сигнатур типов слишком слабое, чтобы это увидеть? Есть ли лучший способ выполнить то, что я пытаюсь сделать?

Было бы довольно тривиально, если бы я просто пытался добавить новый элемент либо в начало, либо в конец списка, но сложная вставка его где-то в середине. В некотором коде перед линзой, который я написал, я использовал сгиб, чтобы выполнить то, что я хотел, но он начинал скручивать более глубоко вложенные части структуры (например, сгиб внутри сгиба внутри сгиба), так что Я повернулся к Control.Lens, чтобы попытаться распутать часть этого беспорядка.

3 ответа

Используя объектив pacakge

Если мы начнем с знания функции id можно использовать как объектив:

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

Затем мы можем перейти к тому, как можно изменить список:

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

Вышесказанное допускает вставку в начале списка. Чтобы сосредоточиться на последних частях списка, мы можем использовать _tail из модуля Control.Lens.Cons.

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

Теперь обобщим это для n-й позиции

> :{
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]

Один последний шаг, чтобы обобщить это для всех типов с Cons Например, мы можем использовать cons или же <|,

> [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"

Я думаю, что простой подход будет разбить проблему в:

  • Функция, которая имеет [a] -> SomeAddtionalData -> [a], который в основном отвечает за преобразование списка в другой список, используя некоторые конкретные данные. Здесь вы можете добавить / удалить элементы из списка и получить новый список
  • Используйте lense для извлечения списка из некоторой вложенной структуры данных, передачи этого списка в определенную выше функцию, установки возвращаемого списка во вложенной структуре данных с использованием lense.

Ваш последний абзац указывает на то, что происходит, когда вы пытаетесь сделать слишком много, используя общую абстракцию, такую ​​как Lens. Эти общие абстракции хороши для каких-то общих целей, а все остальное специфично для вашей проблемы и должно быть построено вокруг простых старых функций (по крайней мере, на начальном этапе в вашем проекте вы можете найти какой-то общий шаблон в базе кода, который можно абстрагировать с помощью типовые занятия и т. д.).

Некоторые комментарии по вашей проблеме:

Ответьте на вопрос: может быть способ сделать то, что вы хотите сделать. Библиотека объективов удивительно универсальна. Чего нет, так это простого или очевидного способа сделать это. Я думаю, что это будет включать в себя partsOf комбинатор но я не уверен.

Комментарии к линзам: Библиотека линз действительно классная и может применяться для решения целого ряда проблем. Моим первоначальным соблазном, когда я изучал библиотеку, было попытаться вписать все в доступ к объективу или мутацию. Я обнаружил, что лучше использовать библиотеку линз, чтобы копаться в моих сложных структурах данных, но после того, как у меня появился простой элемент, лучше использовать более традиционные функциональные приемы, которые я уже знал, а не растягивать библиотеку линз мимо, это полезно предел.

Совет, который вы не просили: вставка элемента в середину списка - плохая идея. Не то чтобы это нельзя было сделать, но это может закончиться операцией O(n^2). ( См. Также этот ответ Stackru.) Лучше всего использовать Zip-списки или другую функциональную структуру данных. В качестве дополнительного преимущества, некоторые из этих структур могут стать At класс, допускающий вставку и удаление с использованием комбинаторов частичных линз.

Другие вопросы по тегам