Search code examples
haskellhaskell-lenslenses

lifo queues as optics

Consider a list of items [a] and a pair of functions

pop :: [a] -> (Maybe a, [a])
pop = headMay &&& tailSafe

push :: a -> [a] -> [a]
push = (:)

which just provide the list with a last in-first out queue structure.

I might be wrong, but the API of this feels very lensy, providing a way to accessing the first element of the list. Still it is neither a Lens nor a Prism.

I was wondering it this could be implemented as a Traversal or some other optics structure

Solution

  • Pushing and popping at the list head can be expressed as a prism -- from an [a] to maybe an (a, [a]), and from an (a, [a]) back to an [a]. That exists in lens as _Cons:

    _Cons @[a] @[b] :: Prism [a] [b] (a, [a]) (b, [b])

    (This only diverges from your API by expressly ruling out getting a non-empty list but not an element from pop, as a (Maybe a, [a]) result type would, in principle, allow.)