Haskell contato tipo di lista

Question

Quindi, solo per divertimento, ho giocato con un tipo CountedList in Haskell, utilizzando i numeri Peano e intelligenti costruttori .

type-safe head e tail sembrano appena davvero cool per me.

E io credo di aver raggiunto il limite di ciò che so come fare

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

. (Ci scusiamo per eventuali errori di trascrizione - la macchina che originariamente scritto questo w / il mio compilatore Haskell è attualmente in giù)

La maggior parte di quello che ho fatto compila w / o un problema, ma mi imbatto in problemi con ofList e filter. Credo di capire il motivo per cui - quando dico ofList :: [a] -> CountedList n a, sto dicendo ofList :: forall n . [a] -> CountedList n a - che l'elenco creato può essere di qualsiasi tipo di conteggio desiderato. Quello che voglio scrivere è l'equivalente di tipo pseudo ofList :: exists n . [a] -> CountedList n a, ma io non so come.

C'è una soluzione che mi permetteva di scrivere funzioni ofList e filter come sto immaginando, o ho raggiunto il limite di quello che posso fare con questo? Ho la sensazione che ci sia qualche trucco con i tipi esistenziali che mi manca.

Answer 1

Non si può scrivere

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

ma è possibile scrivere

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

e passarlo una funzione che rappresenta quello che avrebbe fatto con il risultato di ofList, a patto che il suo tipo è indipendente dalla lunghezza della lista.

A proposito, è possibile garantire l'invariante che il tipo di una lista corrisponde alla sua lunghezza nel sistema tipo, e non affidarsi a costruttori intelligenti:

{-# LANGUAGE GADTs #-}

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

Answer 2

Non è possibile definire ofList o filter questo modo perché sono controlli confondenti tipo di livello con valori di runtime. In particolare, nel tipo di risultato, CountedList n a, il tipo n deve essere determinata in fase di compilazione. Il desiderio implicito è che n dovrebbe essere commisurata alla lunghezza della lista che è il primo argomento. Ma questo chiaramente non può essere conosciuto fino a run-time.

Ora, potrebbe essere possibile definire un typeclass, dire contato, e poi (con l'estensione Haskell appropriata), definire questi come:

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

Ma si avrebbe un momento difficile fare qualsiasi cosa con un risultato del genere, dal momento che le uniche operazioni che CountedListable potrebbe sostegno sarebbe estrarre il conteggio. Non si poteva, dire ottenere il head di tale valore perché la testa non poteva essere definito per tutte le istanze di CountedListable