Haskell zählte Listenentyp

Question

Also habe ich zum Spaß mit einem GreatedList -Typ in Haskell gespielt, wobei ich Peano -Nummern verwendet habe und Smart Constructors.

Typ-Safe head und tail Scheint mir einfach wirklich cool zu sein.

Und ich denke, ich habe die Grenze für das erreicht, was ich weiß,

{-# LANGUAGE EmptyDataDecls #-}
module CountedList (
  Zero, Succ, CountedList,
  toList, ofList, 
  empty, cons, uncons, 
  head, tail, 
  fmap, map, foldl, foldr, filter
) where

import qualified List (foldr, foldl, filter)
import Prelude hiding (map, head, foldl, foldr, tail, filter)

data Zero
data Succ n
data CountedList n a = CL [a]

toList :: CountedList n a -> [a]
toList (CL as) = as

ofList :: [a] -> CountedList n a
ofList [] = empty
ofList (a:as) = cons a $ ofList as

empty :: CountedList Zero a
empty = CL []

cons :: a -> CountedList n a -> CountedList (Succ n) a
cons a = CL . (a:) . toList

uncons :: CountedList (Succ n) a -> (a, CountedList n a)
uncons (CL (a:as)) = (a, CL as)

head :: CountedList (Succ n) a -> a
head = fst . uncons

tail :: CountedList (Succ n) a -> CountedList n a
tail = snd . uncons

instance Functor (CountedList n) where
  fmap f = CL . fmap f . toList

map :: (a -> b) -> CountedList n a -> CountedList n b
map = fmap

foldl :: (a -> b -> a) -> a -> CountedList n b -> a
foldl f a = List.foldl f a . toList

foldr :: (a -> b -> b) -> b -> CountedList n a -> b
foldr f b = List.foldr f b . toList

filter :: (a -> Bool) -> CountedList n a -> CountedList m a
filter p = ofList . List.filter p . toList

(Entschuldigung für Transkriptionsfehler - die Maschine, die ich ursprünglich auf meinem Haskell -Compiler geschrieben habe, ist derzeit ausgefallen.)

Das meiste, was ich getan habe, erstellt mit einem Problem, aber ich stieß auf Probleme mit ofList und filter. Ich glaube, ich verstehe warum - wenn ich sage ofList :: [a] -> CountedList n a, Ich sage ofList :: forall n . [a] -> CountedList n a - Das erstellte Liste kann von jedem gewünschten Zähltyp sein. Was ich schreiben möchte, ist das Äquivalent des Pseudo -Typs ofList :: exists n . [a] -> CountedList n a, aber ich weiß nicht wie.

Gibt es eine Problemumgehung, die mich schreiben lässt ofList und filter Funktionen, wie ich es mir vorstelle, oder habe ich die Grenze dessen erreicht, was ich damit machen kann? Ich habe das Gefühl, dass es einen Trick mit gibt existenzielle Typen dass ich vermisse.

Answer 1

Sie können nicht schreiben

ofList :: [a] -> (exists n. CountedList n a)  -- wrong

Aber du kannst schreiben

withCountedList :: [a] -> (forall n. CountedList n a -> b) -> b

und übergeben es eine Funktion, die darstellt, was Sie mit dem Ergebnis von ofList, solange sein Typ unabhängig von der Länge der Liste ist.

Übrigens können Sie die Invariante sicherstellen, dass der Typ einer Liste ihrer Länge im Typsystem entspricht und sich nicht auf intelligente Konstrukteure verlassen:

{-# LANGUAGE GADTs #-}

data CountedList n a where
    Empty :: CountedList Zero a
    Cons :: a -> CountedList n a -> CountedList (Succ n) a

Answer 2

Sie können nicht definieren ofList oder filter Auf diese Weise, weil sie Überprüfungen auf Typ-Ebene mit Laufzeitwerten verwirrt. Insbesondere im Typ des Ergebniss, CountedList n a, der Typ n muss zur Kompilierungszeit bestimmt werden. Das implizite Wunsch ist das n sollte der Länge der Liste angemessen sein, die das erste Argument ist. Aber das kann eindeutig bis zur Laufzeit bekannt.

Nun könnte es möglich sein, eine Typklasse zu definieren, beispielsweise gezählt, und dann (mit der entsprechenden Haskell -Erweiterung) diese wie folgt:

ofList :: [a] -> (forall n. (CountedListable CountedList n) => CountedList n a)

Aber es fällt Ihnen schwer, etwas mit einem solchen Ergebnis zu tun, da die einzigen Operationen das CountedListable könnte unterstützen würden die Anzahl extrahieren. Sie konnten nicht, sagen Sie das head eines solchen Wertes, weil der Kopf nicht für alle Fälle von definiert werden konnte CountedListable