How to write reverseT without using List?

Question

I need an alternative to reverseT that doesn't use toList. Obviously, this code is incorrect, but demonstrates the idea I was pursuing:

reverseF
  :: (Foldable f, Representable f, Num (Rep f))
  => f a -> f a
reverseF f = tabulate $ \ix -> index f $ last - ix
  where last = length f - 1  -- Incorrect; length -> ?

Does anyone know what I can replace length with, so as to get the last index element offered by tabulate when building an f?

Answer 1

You could assume and use Bounded (Rep f) and Enum (Rep f), i.e., convert Rep f to Int with toEnum, change indices by some Int arithmetic that uses Int counterparts of minBound and maxBound on Rep f (or assume fromEnum minBound == 0), and finally from Int back to Rep f with fromEnum.

Answer 2

Representable does not support reverse in general, because infinite fixed-shape structures are representable but not reversible, e. g. streams:

{-# language DeriveFunctor, TypeFamilies #-}

import Data.Distributive
import Data.Functor.Rep

data Stream a = Cons {hd :: a, tl :: Stream a} deriving Functor

instance Distributive Stream where
  distribute fa = Cons (hd <$> fa) (distribute (tl <$> fa))

data Nat = Z | S Nat

instance Representable Stream where
  type Rep Stream = Nat
  tabulate f      = Cons (f Z) (tabulate (f . S))
  index as Z      = hd as
  index as (S n)  = index (tl as) n

For generic reversal you need finite Rep as in Conal's answer, but I think requiring Traversable by itself would be acceptable and probably more efficient than index and tabulate in most cases. You can reverse using the State applicative:

import Control.Monad.State.Strict

reverseT :: Traversable t => t a -> t a
reverseT ta =
  evalState (traverse (\_ -> gets head <* modify tail) ta)
            (foldl (flip (:)) [] ta)