在没有 unsafeCoerce 的情况下将值更改为 `Conkin.Traversable` 中的索引

Question

使用 conkin 包：https://hackage.haskell.org/package/conkin

我希望能够将任何 Conkin.Traversable 转储到 Tuple 中，将 indices 留在 Tuple 中，所以我可以重建它。

我正在使用一些语言扩展：

{-# LANGUAGE DataKinds                 #-}
{-# LANGUAGE ExistentialQuantification #-}
{-# LANGUAGE GADTs                     #-}
{-# LANGUAGE KindSignatures            #-}
{-# LANGUAGE PolyKinds                 #-}
{-# LANGUAGE RankNTypes                #-}
{-# LANGUAGE ScopedTypeVariables       #-}
{-# LANGUAGE TypeOperators             #-}

模块声明

module TupleDump where

进口

import           Control.Monad.State  (State, runState)
import qualified Control.Monad.State  as State
import           Data.Functor.Compose (getCompose)
import           Data.Functor.Const   (Const (Const), getConst)
import           Conkin               (Dispose (..), Flip (..), Tuple (..))
import qualified Conkin

我不想使用 unsafeCoerce，但看不到解决方法：

import           Unsafe.Coerce        (unsafeCoerce)

让我们将 Index 定义为：

data Index (xs :: [k]) (x :: k) where
  IZ :: Index (x ': xs) x
  IS :: Index xs i -> Index (x ': xs) i

我们可以使用索引从 Tuple:

中提取项目

(!) :: Tuple xs a -> Index xs x -> a x
(!) (Cons x _) IZ      = x
(!) (Cons _ xs) (IS i) = xs ! i

我们应该能够将任何 Conkin.Traversable 的实例和转储到 Tuple 留下一个索引来代替每个实例元素。然后根据索引和元组的结构我们可以重构原来的Traversable结构：

data TupleDump t a = forall xs. TupleDump (t (Index xs)) (Tuple xs a)

toTupleDump :: forall (t :: (k -> *) -> *) (a :: k -> *). Conkin.Traversable t
  => t a -> TupleDump t a
fromTupleDump :: Conkin.Functor t => TupleDump t a -> t a

重构部分很简单：

fromTupleDump (TupleDump inds vals) = Conkin.fmap (vals !) inds

这个问题具体是如何实现的toTupleDump。以下是我迄今为止的最佳尝试：

它涉及很多辅助函数和一个unsafeCoerce

存在量化函子：

data Some (a :: k -> *) = forall (x :: k). Some (a x)

给定一个 Int，构造一些 Index:

mkIndex :: Tuple xs a -> Int -> Some (Index xs)
mkIndex Nil _ = error "Index out of bounds"
mkIndex _ n | n < 0 = error "Index out of bounds"
mkIndex (Cons _ _) 0 = Some IZ
mkIndex (Cons _ xs) n = case mkIndex xs (n - 1) of Some i -> Some $ IS i

给定存在量化函子列表，将它们分组为（翻转的）Tuple：

fromList :: [Some a] -> Some (Flip Tuple a)
fromList [] = Some $ Flip Nil
fromList (Some x : xs) = case fromList xs of
  Some (Flip t) -> Some (Flip (Cons x t))

遍历 Prelude.Applicative（而不是 Conkin.Applicative）

traverseInPrelude :: (Prelude.Applicative f, Conkin.Traversable t)
  => (forall x. a x -> f (b x)) -> t a -> f (t b)
traverseInPrelude fn t =
  Conkin.fmap (unComposeConst . getFlip) . getCompose <$>
    getDispose (Conkin.traverse (Dispose . fmap ComposeConst . fn) t)

newtype ComposeConst a b c = ComposeConst {unComposeConst :: a b}

现在我们可以定义toTupleDump:

toTupleDump t =

我们首先将索引作为 Int 进行跟踪，并将我们的元素转储到普通列表中。由于我们正在使用 (:) 构建列表，因此它将向后。

  let
    nextItem :: forall (x :: k). a x -> State (Int, [Some a]) (Const Int x)
    nextItem x = do
      (i, xs') <- State.get
      State.put (i + 1, Some x : xs')
      return $ Const i
    (res, (_, xs)) = runState (traverseInPrelude nextItem t) (0, [])
  in

现在我们反转列表并将其转换为 Tuple:

  case fromList (reverse xs) of
    Some (Flip (tup :: Tuple xs a)) ->

并且我们需要 fmap 覆盖 res 结构，将所有 Int 更改为 Indexes

      let
        indexedRes = Conkin.fmap (coerceIndex . mkIndex tup . getConst) res

这是unsafeCoerce。由于这种方法涉及结构的两次遍历，我们必须让类型检查器知道在第二次遍历时，类型参数与第一次遍历时相同。

        coerceIndex :: forall x. Some (Index xs) -> Index xs x
        coerceIndex (Some i) = unsafeCoerce i
      in
      TupleDump indexedRes tup

Answer 1

我猜想没有unsafeCoerce是不可能实现toTupleDump的。

问题可以简化为计算fillWithIndexes

data SomeIndex t = forall xs. SomeIndex (t (Index xs))

fillWithIndexes :: forall (t :: (k -> *) -> *) (a :: k -> *). Conkin.Traversable t
  => t a -> SomeIndex t

其中xs是遍历[=16=]类型的值时收集到的类型列表。但是，类型系统不能保证遍历结果 t (Index xs) 会产生相同的类型列表 xs.

如果 t 的 Traversable 实例不遵守 Traversable 法则，则可以编造一个实际更改类型的实现。

data T a = TBool (a Bool) | TChar (a Char)
instance Conkin.Functor T where
  fmap f (TBool a) = TBool (f a)
  fmap f (TChar a) = TChar (f a)

instance Conkin.Foldable T where
  foldr f z (TBool a) = f a z
  foldr f z (TChar a) = f a z

instance Conkin.Traversable T where
  traverse f (TBool a) = Conkin.pure (Compose (TChar undefined))
  traverse f (TChar a) = Conkin.pure (Compose (TBool undefined))

我们不能通过假设 Traversable 定律成立来排除这种情况吗？是的，我们可以排除，但是typechecker不能，也就是说我们必须使用unsafeCoerce.

在没有 unsafeCoerce 的情况下将值更改为 `Conkin.Traversable` 中的索引

Change values to indices in a `Conkin.Traversable` without `unsafeCoerce`

haskell

traversal

existential-type

data-kinds