haskellfunctorshifttraversablefoldable

Is there an equivalent to head/tail for Foldable functors in general?


I would like to express the following Haskell code, using only functor algebra (i.e. - not relying on any specific container type, such as List):

ys = zipWith (+) (head xs : repeat 0)
                 (tail xs ++ [y])

It seems to me that there ought to be a way to do this, relying only on Foldable (or, maybe, Traversable), but I can't see it.

I'm wondering:

  1. Is there a general notion of first and rest for Foldable/Traversable functors?
  2. Is there an accepted idiomatic way, using only functor algebra, to shift the contents of a Foldable/Traversable functor? (Note that the computation above might be described in English as, "Shift in one value from the right, and add back the value that falls of on the left to the new first value.")

Solution

  • The first part of your question (combining the first value of a structure with one thing and leaving the rest the same) can be done in a straightforward way with Traversable. We'll use State, start it off with the function we want to apply, and modify it to id immediately.

    onlyOnHead :: Traversable t => (a -> a) -> t a -> t a
    onlyOnHead f xs = evalState (traverse go xs) f where
        go x = do
            fCurrent <- get
            put id
            return (fCurrent x)
    

    You can rotate elements with a similar idea: we'll rotate a list, and stuff that in our State as the thing to draw elements from.

    rotate :: Traversable t => t a -> t a
    rotate xs = evalState (traverse go xs) (rotateList (toList xs)) where
        rotateList [] = []
        rotateList vs = tail vs ++ [head vs]
    
        go _ = do
            v:vs <- get
            put vs
            return v