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

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

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

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

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


list haskell lenses
person Orclev    schedule 28.08.2013    source источник
comment
Рассматривали ли вы что-то вроде ziplist вместо обычного списка? Это упростило бы вставку элемента до или после элемента фокуса.   -  person kqr    schedule 28.08.2013
comment
Я думал об этом, но то, как построена исходная структура данных, было бы трудно преобразовать в ziplist, поэтому мне, вероятно, придется преобразовать ее постфактум, что означает совершенно отдельную иерархию типов только для содержания ziplists. Либо так, либо я конвертирую из списка в ziplist и обратно каждый раз, когда мне нужно сделать вставку, что я мог бы сделать, но не похоже, что это лучше, чем просто свернуть весь список в первую очередь.   -  person Orclev    schedule 28.08.2013

Ответы (3)


arrow_upward
7
arrow_downward

Использование пакета lens

Если мы начнем с знания, что функцию 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 instance мы можем использовать 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"
person Davorak    schedule 23.10.2015

arrow_upward
2
arrow_downward

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

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

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

person Ankur    schedule 28.08.2013
comment
Я думаю, что вы что-то упустили в последнем абзаце, это то, что произошло, когда я не использовал линзы. Вложенный характер данных означал, что я просматривал несколько уровней списков, используя складки, чтобы найти место, в которое я хотел вставить новый элемент. Использование линз для обхода по крайней мере родительских списков кажется чище, хотя на данный момент кажется, что я могу застрять по крайней мере с одним сгибом, чтобы выполнить фактическую вставку. - person Orclev; 28.08.2013

arrow_upward
2
arrow_downward

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

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

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

Совет, о котором вы не просили. Вставка элемента в середину списка — плохая идея. Не то чтобы это невозможно сделать, но это может оказаться операцией O (n ^ 2). (см. также этот ответ StackOverflow.) Zip-списки или другие < лучше использовать href="http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf" rel="nofollow noreferrer">функциональную структуру данных. В качестве дополнительного преимущества некоторые из этих структур можно сделать экземплярами класса At, позволяющими вставлять и удалять с помощью комбинаторов частичной линзы.

person John F. Miller    schedule 28.08.2013