haskell - 如何在不使用List的情况下编写reverseT？

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 with，从而得到 tabulate提供的最后一个索引元素构建 f 时?

Answer 1

Representable不支持reverse一般来说，因为无限固定形状的结构是可表示但不可逆的，例如。 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 更有效和 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)