Вставка в список в определенном месте с помощью линз
Я пытаюсь выполнить манипулирование вложенной структурой данных, содержащей списки элементов. После осмотра разных подходов я наконец-то остановился на линзах как на лучшем способе сделать это. Они отлично работают для поиска и изменения определенных элементов структуры, но пока я не знаю, как добавлять новые элементы.
Из того, что я прочитал, я не могу технически использовать Обход, поскольку он нарушает законы Обхода, чтобы вставить новый элемент в список, и это предполагает, что я мог бы даже выяснить, как это сделать, используя Обход в первую очередь (Я все еще довольно слаб с 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
класс, допускающий вставку и удаление с использованием комбинаторов частичных линз.