Как написать reverseT без использования List?

Question

Мне нужна альтернатива reverseT это не использует toList, Очевидно, этот код неверен, но демонстрирует идею, которую я преследовал:

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 -> ?

Кто-нибудь знает, что я могу заменить length с, чтобы получить последний элемент индекса, предлагаемый tabulate при создании f?

Answer 1

Representable не поддерживается reverse в общем, потому что бесконечные структуры фиксированной формы представимы, но не обратимы, например, потоки:

{-# 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

Для общего обращения вам нужно конечное Rep как в ответе Конала, но я думаю, требуя Traversable само по себе было бы приемлемым и, вероятно, более эффективным, чем index а также tabulate в большинстве случаев. Вы можете повернуть вспять, используя State аппликативны:

import Control.Monad.State.Strict

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

Answer 2

Вы могли бы принять и использовать Bounded (Rep f) а также Enum (Rep f)то есть конвертировать Rep f в Int с toEnumизменить индексы на несколько Int арифметика, которая использует Int аналоги minBound а также maxBound на Rep f (или предположим, fromEnum minBound == 0) и, наконец, из Int вернуться к Rep f с fromEnum,