Wie Länge kommentierten Listen in Haskell

Question

Anscheinend zu verwenden, mit einigen GHC Erweiterungen ist es möglich, eine Art von Liste zu definieren, die Länge in der Art codiert, wie folgt aus:

{-# LANGUAGE GADTs, EmptyDataDecls #-} 

data Z 
data S a 

data List l a where 
    Nil :: List Z a 
    Cons :: a -> List l a -> List (S l) a 

Während ich sehen, warum dies kann nützlich sein, ich habe Probleme, es zu benutzen.

Wie kann man eine solche Liste erstellen? (Abgesehen davon, es in das Programm zu kodieren.)

Angenommen, Sie möchten ein Programm erstellen, das zwei solche Listen vom Terminal liest und ihr Punktprodukt berechnet. Während es einfach ist, die eigentliche multiplikative Funktion zu implementieren, wie kann das Programm die Daten lesen?

Können Sie mich auf einen vorhandenen Code verweisen, der diese Techniken verwendet?

Answer 1

Sie müssen die Länge der Liste nicht fest codieren; stattdessen können Sie den folgenden Art definieren:

data UList a where 
    UList :: Nat n => List n a -> UList a 

wo

class Nat n where 
    asInt :: n -> Int 

instance Nat Z where 
    asInt _ = 0 

instance Nat n => Nat (S n) where 
    asInt x = 1 + asInt (pred x) 
     where 
     pred = undefined :: S n -> n 

und wir auch

fromList :: [a] -> UList a 
fromList [] = UList Nil 
fromList (x:rest) = 
    case fromList rest of 
     UList xs -> UList (Cons x xs) 

Dieses Setup Sie Listen, deren Längen erstellen können haben, werden bei der Kompilierung nicht bekannt ; Sie können auf die Länge zugreifen, indem Sie eine Musterübereinstimmung case ausführen, um den Typ aus dem Existential-Wrapper zu extrahieren, und dann die Klasse Nat verwenden, um den Typ in eine Ganzzahl umzuwandeln.

Sie könnten sich fragen, welchen Vorteil ein Typ hat, von dem Sie den Wert zur Kompilierzeit nicht kennen; Die Antwort lautet: Obwohl Sie nicht wissen, was der Typ sein wird, können Sie immer noch Invarianten erzwingen. Beispielsweise wird der folgende Code garantiert die Länge der Liste nicht ändern:

mapList :: (a -> b) -> List n a -> List n b 

Und wenn wir Addition mit einer Art Familie genannt haben, sagen wir, Add, dann können wir

concatList :: List m a -> List n a -> List (Add m n) a 

schreiben

, die die Invariante erzwingt, dass die Verkettung zweier Listen eine neue Liste mit der Summe der beiden Längen ergibt.

Answer 2

Sie müssen es ziemlich hart-Code, da der Typ ist natürlich zur Kompilierzeit festgelegt und die Turing-Vollständigkeit der GHC-Typ-Checker kann nicht praktikabel missbraucht werden, um sie "allein" zu generieren. Das ist jedoch nicht so dramatisch, wie es sich anhört: Sie müssen den Annotationstyp Länge nur einmal schreiben. Der Rest kann um ohne Angabe einer bestimmten Länge, wenn auch mit etwas seltsam aussehenden Klasse erfolgen:

class LOL l where 
    lol :: [a] -> l a 

instance LOL (List Z) where 
    lol _ = Nil 

instance (LOL (List n)) => LOL (List (S n)) where 
    lol (x:xs) = Cons a $ lol xs 
    lol [] = error "Not enough elements given to make requested type length." 

Dann können Sie einfach so etwas wie

type Four = S(S(S(S Z))) 

get4Vect :: Read a => IO (List Four a) 
get4Vect = lol . read <$> getLine -- For input format [1,2,3,4]. 

---

I shan verwenden‘ t diskutieren Template Haskell hier, die natürlich alles automatisch zur Kompilierzeit leicht generieren kann.

Answer 3

Die Längencodierung funktioniert während der Kompilierzeit, also kann der Typüberprüfer natürlich nicht die Längen von Listen überprüfen, die zur Laufzeit aus z. Benutzereingabe. Die Idee ist, dass Sie alle Laufzeitlisten in einen existentiellen Typ umbrechen, der den length-Parameter verbirgt, und dann müssen Sie Beweise über die Länge liefern, um die Liste zu verwenden.

Zum Beispiel:

{-# LANGUAGE GADTs #-} 
{-# LANGUAGE DataKinds #-} 
{-# LANGUAGE PolyKinds #-} 
{-# LANGUAGE ScopedTypeVariables #-} 

module Lists where 

data Nat = Z | S Nat 

data List l a where 
    Nil :: List Z a 
    Cons :: a -> List n a -> List (S n) a 

data DynList a where 
    DynList :: List l a -> DynList a 

data Refl a b where 
    Refl :: Refl a a 

fromList :: [a] -> DynList a 
fromList []  = DynList Nil 
fromList (x:xs) = cons (fromList xs) where 
    cons (DynList rest) = DynList $ Cons x rest 

toList :: List l a -> [a] 
toList Nil = [] 
toList (Cons x xs) = x : toList xs 

dot :: Num a => List l a -> List l a -> List l a 
dot Nil Nil = Nil 
dot (Cons x xs) (Cons y ys) = Cons (x*y) (dot xs ys) 

haveSameLength :: List l a -> List l' b -> Maybe (Refl l l') 
haveSameLength Nil Nil     = Just Refl 
haveSameLength (Cons _ xs) (Cons _ ys) = case haveSameLength xs ys of 
    Just Refl -> Just Refl 
    Nothing -> Nothing 
haveSameLength _ _      = Nothing 

main :: IO() 
main = do 
    dlx :: DynList Double <- fmap (fromList . read) getLine 
    dly :: DynList Double <- fmap (fromList . read) getLine 

    case (dlx, dly) of 
     (DynList xs, DynList ys) -> case haveSameLength xs ys of 
      Just Refl -> print $ toList $ dot xs ys 
      Nothing -> putStrLn "list lengths do not match" 

Hier DynList ist eine Liste mit dynamischer Länge (das heißt die Länge nur zur Laufzeit bekannt ist), die ein List richtig getippt wickelt. Jetzt haben wir eine dot Funktion, die das Skalarprodukt für zwei Listen gleicher Länge berechnet. Wenn wir die Listen von stdin wie im Beispiel lesen, müssen wir beweisen, dass die Listen tatsächlich identische Längen haben . Der "Beweis" ist hier der Refl Konstruktor. Die Art, wie der Konstruktor deklariert wird, bedeutet, dass, wenn wir einen Wert vom Typ Refl a b liefern können, a und b vom selben Typ sein müssen. Daher verwenden wir hasSameLength, um die Typen und Musterübereinstimmung auf dem produzierten Refl Wert zu überprüfen, und das gibt dem Typ-Checker genügend Informationen, die es uns dot in den zwei Laufzeitlisten aufrufen kann.

Was bedeutet dies im Wesentlichen, dass der Typ-Checker uns zwingen wird, manuell die Länge einer Liste zu überprüfen, die nicht zur Kompilierzeit bekannt ist, um den Code zu kompilieren.