Складной рекурсивный тип семейства

Question

Я пытаюсь сложить данные с фантомным типом [*]. Вот упрощенная версия моего кода

{-# LANGUAGE DataKinds, KindSignatures #-}

module Stack where
import Data.HList
import Data.Foldable as F

data T (a :: [*]) = T (Tagged a String)
(!++!) :: T a -> T b -> T (HAppendList a b)
(T a) !++! (T b) = T (Tagged (untag a ++ untag b))


a = T (Tagged "1") :: T '[Int]
b = T (Tagged "-- ") :: T '[]
ab = a !++! b :: T '[Int]

Я хотел бы оператор сгиба

(!++*) :: (Foldable t ) =>  T a -> t (T '[]) -> T a
a !++* t = F.foldl (!++!) a t

Но это не работает. Компилятор, который a а также HAppendList a '[] отличаются, хотя они и не являются.

Почему компиляция не может объединиться HAppendList a '[] а также a?

(Я не могу сделать фолд вручную в GHCI, хотя :t a !++! b !++! b !++! b => T '[Int]

Answer 1

Обратите внимание на определение HAppendList:

type family HAppendList (l1 :: [k]) (l2 :: [k]) :: [k]
type instance HAppendList '[] l = l
type instance HAppendList (e ': l) l' = e ': HAppendList l l'

Ты и я это знаем [] это левая и правая идентичность ++, но компилятор знает только о левой идентичности:

happend' :: T a -> T b -> T (HAppendList a b)
happend' (T (Tagged a)) (T (Tagged b)) = (T (Tagged (a++b)))

-- Doesn't typecheck 
leftIdentity' :: T a -> T '[] -> T a 
leftIdentity' x y = happend' x y 

rightIdentity' :: T '[] -> T a -> T a 
rightIdentity' x y = happend' x y 

Вы должны были бы иметь

type instance HAppendList '[] l = l
type instance HAppendList l '[] = l
type instance HAppendList (e ': l) l' = e ': HAppendList l l'

чтобы компилятор знал о левой и правой идентичности; но они будут перекрывать друг друга, так что это не проверка типа. Вы можете просто перевернуть аргументы, однако:

(!+++!) :: T a -> T b -> T (HAppendList a b) 
(!+++!) (T (Tagged x)) (T (Tagged y)) = T (Tagged (y ++ x))

(!++*) :: Foldable t => T a -> t (T '[]) -> T a
a !++* t = F.foldl (flip (!+++!)) a t

С помощью семейств закрытых типов, представленных в ghc 7.8, вы можете решить эту проблему:

type family (++) (a :: [k]) (b :: [k]) :: [k] where 
  '[] ++ x = x
  x ++ '[] = x
  (x ': xs) ++ ys = x ': (xs ++ ys)

happend :: T a -> T b -> T (a ++ b)
happend (T (Tagged a)) (T (Tagged b)) = (T (Tagged (a++b)))

leftIdentity :: T a -> T '[] -> T a 
leftIdentity x y = happend x y 

rightIdentity :: T '[] -> T a -> T a 
rightIdentity x y = happend x y