gpt4 book ai didi

haskell - 折叠递归类型族

转载 作者:行者123 更新时间:2023-12-05 01:03:50 24 4
gpt4 key购买 nike

我正在尝试使用 [*] 类型的幻影类型折叠数据。这是我的代码的简化版本

{-# 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]

最佳答案

注意 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

关于haskell - 折叠递归类型族,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24252730/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com