Накопление [State sa] результатов

Question

Что я сделал

Я обнаружил, что пишу что-то вроде "рендерера", где в какой-то момент у меня был список переходов состояний:

[State String [a]]

Я хотел применить их один за другим.Я мог сделать это с помощью sequence, что привело меня к

State String [[a]]

Затем мне пришлось сгладить результат из списков списков в список.Я мог бы сделать это с помощью fmapping concat и получить желаемый результат

State String [a]

---

Пока все хорошо

Но чтобы это сработалоМои результаты должны были быть списками.Разве это не должно работать с более общим типом, таким как Traversable, Foldable или даже просто Monoid.

Я понимаю, что я получил список результатов, потому что я начал с списка переходов состояний и последовательность сохраняет эту форму.Итак, если я приму это как данность, мой первый вопрос будет

• Как мне преобразовать State String [a] в State String a

Мой второй вопрос

• можно ли это обобщить еще дальше, так что мои входные данные не обязательно должны быть списком, а могут быть более общего типа, например Traversable?.

---

Или, короче говоря

• Как применить набор переходов состояний один за другим при накоплении результатов?Каковы минимальные ограничения типа для типа коллекции и типа результата?

Answer 1

GHC 8.6+ предоставляют другой способ сделать это, возможно, более прямой.Он добавил новый тип Ap к Data.Monoid, который обрабатывает случай подъема экземпляра Monoid внутреннего типа над контекстом Applicative.

$ghci
GHCi, version 8.6.1: http://www.haskell.org/ghc/  :? for help
Prelude> import Data.Monoid
Prelude Data.Monoid> :t getAp . foldMap Ap
getAp . foldMap Ap
  :: (Foldable t, Applicative f, Monoid a) => t (f a) -> f a

Это обобщает[State String [a]] -> State String [a] в довольно минимальной форме.Фактически, избегая sequence, это снижает требование Traversable до Foldable.(Ограничение Monad на sequence является историческим артефактом, и sequenceA существует, чтобы снизить его до Applicative, поэтому я не беспокоюсь о разнице там.) Этот подход имеет дополнительное незначительное эксплуатационное отличие по сравнению с использованиемsequence - объединяет моноидальное соединение и аппликативную последовательность в один проход.Будут некоторые комбинации типов, где это более эффективно, и комбинации типов, где это может быть менее эффективно из-за ассоциативности.Это зависит от того, имеет ли mappend смещение ассоциативности, которое соответствует смещению, которое создает foldMap.

Answer 2

Как конвертировать State String [a] в State String a

Поскольку State s - это Functor, этот вопрос эквивалентен запросу: Как мне конвертировать[a] в a?

Для этого вы можете использовать mconcat .

Чтобы применить это к State, вы можете комбинировать fmap с mconcat.

можно ли это обобщить еще дальше, так что мои входные данные не обязательно должны быть списком, но могут иметь более общий тип, например Traversable ?.

Да, опять же, основной вопрос - как превратить любой контейнер t a в a.Вам не нужно Traversable для этого;Foldable будет делать.В частности, рассматриваемой функцией является fold .

. Снова объедините fold с fmap для достижения желаемого результата.