代码之家 › 专栏 › 技术社区 › dbanas

如何在不使用List的情况下编写reverseT?

representable foldable reverse haskell

3

dbanas · 技术社区 · 6 年前

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 ?

2 回复 | 直到 6 年前

1

Conal 6 年前

你可以假设并使用 Bounded (Rep f) 和 Enum (Rep f) Rep f 到 Int 具有 toEnum 内景 使用的算术副本 minBound maxBound 在 (或假设 fromEnum minBound == 0 内景 回到 代表f fromEnum .

2

3

András Kovács 6 年前

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)