Ist es möglich, diese Funktion in Haskell zu schreiben?

Question

Ich lerne abhängige Arten: In Haskell ich den kanonischen Typen

data Vec ∷ Type → Nat → Type where 
    Nil ∷ Vec a Z 
    (:-) ∷ a → Vec a n → Vec a (S n) 

und implementiert die meisten Funktionen von Data.List aber ich weiß nicht, wie zu schreiben, wenn überhaupt, Funktionen wie

definiert habe

delete ∷ Eq a ⇒ a → Vec a n → Vec a (??) 

da die Länge des Ergebnisses nicht bekannt ist. Ich habe es in Agda gefunden und es wird auf diese Weise

delete : {A : Set}{n : Nat}(x : A)(xs : Vec A (suc n)) → x ∈ xs → Vec A n 
delete   .x (x ∷ xs) hd = xs 
delete {A}{zero } _ ._  (tl()) 
delete {A}{suc _} y (x ∷ xs) (tl p) = x ∷ delete y xs p 

implementiert Wenn ich das richtig verstehe delete es mit der constrain von x ist ein Element der xs, in diesem Fall definiert ist einfach x entfernen und subtrahiert 1 von der Länge. Kann ich in Haskell so etwas schreiben?

Answer 1

Das Problem ist, dass Sie einen abhängigen Quantifizierer benötigen, den Haskell derzeit nicht besitzt. I.e. der (x : A)(xs : Vec A (suc n)) → ... Teil ist nicht direkt ausdrückbar. Sie können wahrscheinlich etwas mit Singletons kochen, aber es wird wirklich hässlich und kompliziert.

definieren würde ich nur

delete ∷ Eq a ⇒ a → Vec a (S n) → Maybe (Vec a n) 

und mit ihm in Ordnung sein. Ich würde auch die Reihenfolge der Argumente zu Vec ändern, um es möglich zu machen, Applicative, Traversable und andere Instanzen zur Verfügung zu stellen.

---

Eigentlich nein. Um delete Sie gerade zu definieren müssen einen Index zur Verfügung zu stellen, bei dem löschen:

{-# LANGUAGE GADTs, DataKinds #-} 

data Nat = Z | S Nat 

data Index n where 
    IZ :: Index n 
    IS :: Index n -> Index (S n) 

data Vec n a where 
    Nil :: Vec Z a 
    (:-) :: a -> Vec n a -> Vec (S n) a 

delete :: Index n -> Vec (S n) a -> Vec n a 
delete IZ (x :- xs)  = xs 
delete (IS n) (x :- (y :- xs)) = x :- delete n (y :- xs) 

Beachten Sie, dass x ∈ xs ist nichts anderes als ein reich getippt Index.

---

Hier ist eine Lösung mit Singletons:

{-# LANGUAGE GADTs, DataKinds, PolyKinds, KindSignatures, UndecidableInstances, TypeFamilies, RankNTypes, TypeOperators #-} 

infixr 5 :- 

data Nat = Z | S Nat 

data family Sing (x :: a) 

data instance Sing (b :: Bool) where 
    STrue :: Sing True 
    SFalse :: Sing False 

data instance Sing (n :: Nat) where 
    SZ :: Sing Z 
    SS :: Sing n -> Sing (S n) 

type family (:==) (x :: a) (y :: a) :: Bool 

class SEq a where 
    (===) :: forall (x :: a) (y :: a). Sing x -> Sing y -> Sing (x :== y) 

type instance Z :== Z = True 
type instance S n :== Z = False 
type instance Z :== S m = False 
type instance S n :== S m = n :== m 

instance SEq Nat where 
    SZ === SZ = STrue 
    SS n === SZ = SFalse 
    SZ === SS m = SFalse 
    SS n === SS m = n === m 

data Vec xs a where 
    Nil :: Vec '[] a 
    (:-) :: Sing x -> Vec xs a -> Vec (x ': xs) a 

type family If b x y where 
    If True x y = x 
    If False x y = y 

type family Delete x xs where 
    Delete x '[]  = '[] 
    Delete x (y ': xs) = If (x :== y) xs (y ': Delete x xs) 

delete :: forall (x :: a) xs. SEq a => Sing x -> Vec xs a -> Vec (Delete x xs) a 
delete x Nil  = Nil 
delete x (y :- xs) = case x === y of 
    STrue -> xs 
    SFalse -> y :- delete x xs 

test :: Vec '[S Z, S (S (S Z)), Z] Nat 
test = delete (SS (SS SZ)) (SS SZ :- SS (SS (SS SZ)) :- SS (SS SZ) :- SZ :- Nil) 

Hier stellen wir Index Vec s durch Listen ihrer Elemente und speichern Singletons als Elemente von Vektoren. Wir definieren auch SEq, was eine Typklasse ist, die eine Methode enthält, die zwei Singletons empfängt und entweder einen Beweis der Gleichheit der von ihnen geförderten Werte oder ihre Ungleichheit zurückgibt. Als nächstes definieren wir eine Typfamilie Delete, die wie üblich delete für Listen ist, aber auf der Typenebene. Schließlich in der tatsächlichen delete wir Muster übereinstimmen auf x === y und damit offenbaren, ob x ist gleich y oder nicht, was die Art der Familie zu berechnen macht.