[haskell] 완전히 종속적 인 연결 만들기

Program / 글쓴이

연결에 대한 좋은 사실은 방정식에서 두 가지 변수를 아는 경우입니다.

a ++ b = c

그런 다음 세 번째를 알고 있습니다.

나는 기능적으로 의존성을 사용하기 위해이 아이디어를 내 자신의 concat에서 포착하고 싶습니다. 

{-# Language DataKinds, GADTs, FlexibleContexts, FlexibleInstances, FunctionalDependencies, KindSignatures, PolyKinds, TypeOperators, UndecidableInstances #-}
import Data.Kind (Type)

class Concatable
   (m  :: k -> Type)
   (as :: k)
   (bs :: k)
   (cs :: k)
   | as bs -> cs
   , as cs -> bs
   , bs cs -> as
   where
     concat' :: m as -> m bs -> m cs

이제는 이기종 목록을 다음과 같이 활용합니다.

data HList ( as :: [ Type ] ) where
  HEmpty :: HList '[]
  HCons  :: a -> HList as -> HList (a ': as)

그러나 나는 이러한 선언 할 때 Concatable나는 문제가있는

instance Concatable HList '[] bs bs where
  concat' HEmpty bs = bs
instance
  ( Concatable HList as bs cs
  )
    => Concatable HList (a ': as) bs (a ': cs)
  where
    concat' (HCons head tail) bs = HCons head (concat' tail bs)

세 번째 기능 의존성을 만족시키지 않습니다. 또는 오히려 컴파일러는 우리가하지 않는다고 생각합니다. 이는 컴파일러가 두 번째 인스턴스에서 그렇다고 생각하기 때문입니다 bs ~ (a ': cs). 그리고 경우에 해당 될 수 있습니다 Concatable as (a ': cs) cs.

세 가지 종속성이 모두 충족되도록 인스턴스를 조정하려면 어떻게해야합니까?

답변

따라서 의견에서 알 수 있듯이 GHC는 자체적으로 파악하지 않지만 약간의 유형 수준 프로그래밍으로 도울 수 있습니다. 몇 가지를 소개하겠습니다 TypeFamilies. 이러한 모든 기능은 목록 조작을 유형 레벨로 올린 간단한 번역입니다.

-- | This will produce the suffix of `cs` without `as`
type family DropPrefix (as :: [Type]) (cs :: [Type]) where
  DropPrefix '[] cs = cs
  DropPrefix (a ': as) (a ': cs) = DropPrefix as cs

-- Similar to the logic in the question itself: list concatenation. 
type family Concat (as :: [Type]) (bs :: [Type]) where
  Concat '[] bs = bs
  Concat (head ': tail) bs = head ': Concat tail bs

-- | Naive list reversal with help of concatenation.
type family Reverse (xs :: [Type]) where
  Reverse '[] = '[]
  Reverse (x ': xs) = Concat (Reverse xs) '[x]

-- | This will produce the prefix of `cs` without `bs`
type family DropSuffix (bs :: [Type]) (cs :: [Type]) where
  DropSuffix bs cs = Reverse (DropPrefix (Reverse bs) (Reverse cs))

-- | Same definition of `HList` as in the question
data HList (as :: [Type]) where
  HEmpty :: HList '[]
  HCons :: a -> HList as -> HList (a ': as)

-- | Definition of concatenation at the value level
concatHList :: (cs ~ Concat as bs) => HList as -> HList bs -> HList cs
concatHList HEmpty bs = bs
concatHList (HCons head tail) bs = HCons head (concatHList tail bs)

이 도구를 사용하면 실제로 시간 목표를 달성 할 수 있지만 먼저 원하는 속성으로 함수를 정의합시다.

  • 과 에서 추론 cs하는 능력asbs
  • 과 에서 추론 as하는 능력bscs
  • 과 에서 추론 bs하는 능력ascs

짜잔 :

concatH ::
     (cs ~ Concat as bs, bs ~ DropPrefix as cs, as ~ DropSuffix bs cs)
  => HList as
  -> HList bs
  -> HList cs
concatH = concatHList

테스트 해보자.

foo :: HList '[Char, Bool]
foo = HCons 'a' (HCons True HEmpty)

bar :: HList '[Int]
bar = HCons (1 :: Int) HEmpty
λ> :t concatH foo bar
concatH foo bar :: HList '[Char, Bool, Int]
λ> :t concatH bar foo
concatH bar foo :: HList '[Int, Char, Bool]

그리고 마지막 목표 :

class Concatable (m :: k -> Type) (as :: k) (bs :: k) (cs :: k)
  | as bs -> cs
  , as cs -> bs
  , bs cs -> as
  where
  concat' :: m as -> m bs -> m cs

instance (cs ~ Concat as bs, bs ~ DropPrefix as cs, as ~ DropSuffix bs cs) =>
         Concatable HList as bs cs where
  concat' = concatH
λ> :t concat' HEmpty bar
concat' HEmpty bar :: HList '[Int]
λ> :t concat' foo bar
concat' foo bar :: HList '[Char, Bool, Int]
λ> :t concat' bar foo
concat' bar foo :: HList '[Int, Char, Bool]

답변