不用List怎么写reverseT？

Question

我需要一个不使用 toList 的 reverseT 替代品。显然，这段代码是不正确的，但展示了我追求的想法：

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，以便在构建f时获得tabulate提供的最后一个索引元素？

Answer 1

您可以假设并使用 Bounded (Rep f) 和 Enum (Rep f)，即将 Rep f 转换为 Int toEnum，将索引更改为 [=13] =] 在 Rep f 上使用 minBound 和 maxBound 对应的 Int 算术（或假设 fromEnum minBound == 0），最后从 Int 回到 Rep f 与 fromEnum.

Answer 2

Representable一般不支持reverse，因为无限定形结构是可表示的，但不可逆，e。 G。流：

{-# 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，如 Conal 的回答，但我认为单独要求 Traversable 是可以接受的，并且可能比 index 和 [=17= 更有效] 大多数情况下。您可以使用 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)

不用List怎么写reverseT？

How to write reverseT without using List?

haskell

reverse

foldable

representable