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?

With [`partsOf`](https://hackage.haskell.org/package/lens-4.17/docs/Control-Lens-Traversal.html#v:partsOf) you can get `over (partsOf traverse) reverse :: Traversable t => t ~> t` for any `Traversable t`. The `Traversable` constraint also ensures that we preserve the shape of `t`. — Iceland_jack, Aug 12 '18 at 21:38

score 3 · Answer 1 · answered Aug 12 '18 at 22:34

3

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)

answered Aug 12 '18 at 22:34

András Kovács

29,931
3
53
99

1

Extra challenge: do without partial functions by using a different functor. – dfeuer Aug 12 '18 at 23:27
Thanks! Your solution looks like it goes through List as an intermediate state. Is that not the case? – dbanas Aug 13 '18 at 14:27
@dbanas yes. With the `Traversable` solution, you can't do significantly better. – András Kovács Aug 13 '18 at 14:59
1

@dfeuer Solution to extra challenge [here](https://gist.github.com/AndrasKovacs/cfc22a19c91100f4c7c350833dd86434). – András Kovács Aug 13 '18 at 15:14
Nice! I suspect you really do need such mild shenanigans (plugins or `unsafeCoerce`) for efficiency, but it would be double-extra cool to avoid them somehow. – dfeuer Aug 13 '18 at 18:13
One advantage of using `Representable` over `State` is amenability to massively parallel evaluation. – Conal Sep 05 '18 at 17:11

score 1 · Accepted Answer · answered Aug 12 '18 at 21:32

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.

How to write reverseT without using List?

2 Answers2