Haskell: Specificare vincoli di uguale lunghezza delle liste nel sistema tipo

Question

In Haskell, mi hanno spesso una funzione come f, che accetta una lista e restituisce una lista di uguale lunghezza:

f :: [a] -> [a] -- length f(xs) == length xs 

Allo stesso modo, potrei avere una funzione come g, che accetta due liste che dovrebbe essere di uguale lunghezza:

g :: [a] -> [a] -> ... 

Se f e g sono tipizzati come sopra, allora runtime errori può causare loro vincoli con indicazioni di lunghezza non sono satisf ied. Vorrei quindi codificare questi vincoli nel sistema dei tipi. Come potrei farlo?

Si prega di notare che sto cercando un framework pratico che possa essere utilizzato nelle situazioni di tutti i giorni, aggiungendo il minimo di overhead intuitivo al codice possibile. Sono particolarmente interessato a sapere come si tratterebbe con f e g; cioè, vorresti aggiungere i vincoli relativi alla lunghezza ai loro tipi, come richiesto qui, o li lasceresti con i tipi sopra indicati per la semplicità del codice?

Answer 1

Il codice seguente è adattato da Gabriel Gonzalez's blog in combinazione con alcune informazioni fornite nei commenti:

{-# LANGUAGE GADTs, DataKinds #-} 

data Nat = Z | S Nat 

-- A List of length 'n' holding values of type 'a' 
data List n a where 
    Nil :: List Z a 
    Cons :: a -> List m a -> List (S m) a 

-- Just for visualization (a better instance would work with read) 
instance Show a => Show (List n a) where 
    show Nil = "Nil" 
    show (Cons x xs) = show x ++ "-" ++ show xs 

g :: (a -> b -> c) -> List n a -> List n b -> List n c 
g f (Cons x xs) (Cons y ys) = Cons (f x y) $ g f xs ys 
g f Nil Nil = Nil 

l1 = Cons 1 (Cons 2 (Nil)) :: List (S (S Z)) Int 
l2 = Cons 3 (Cons 4 (Nil)) :: List (S (S Z)) Int 
l3 = Cons 5 (Nil) :: List (S Z) Int 

main :: IO() 
main = print $ g (+) l1 l2 
     -- This causes GHC to throw an error: 
     -- print $ g (+) l1 l3 

Questa definizione lista alternativa (utilizzando GADTs e DataKinds) codifica la lunghezza di una lista nel suo genere. Se si definisce quindi la funzione g :: List n a -> List n a -> ..., il sistema di tipi si lamenterà se gli elenchi non hanno la stessa lunghezza.

Nel caso in cui questo sarebbe (comprensibilmente) una complicazione eccessiva per te, non sono sicuro che usare il sistema di tipi sarebbe la strada da percorrere. Il modo più semplice è definire g utilizzando una monade/applicativo (ad esempio Maybe o Either), lasciare che g aggiunga elementi all'elenco in base a entrambi gli input e in sequenza il risultato. Cioè

g :: (a -> b -> c) -> [a] -> [b] -> Maybe [c] 
g f l1 l2 = sequence $ g' f l1 l2 
    where g' f (x:xs) (y:ys) = (Just $ f x y) : g' f xs ys 
     g' f [] [] = [] 
     g' f _ _ = [Nothing] 

main :: IO() 
main = do print $ g (+) [1,2] [2,3,4] -- Nothing 
      print $ g (+) [1,2,3] [2,3,4] -- Just [3,5,7] 

Answer 2

La mancanza che si osserva è perché l'informazione di lunghezza non fa parte del tipo dell'elenco; poiché il controllore del tipo intende ragionare sui tipi, non è possibile specificare gli invarianti nelle proprie funzioni a meno che gli invarianti non siano nello tipo degli argomenti stessi o sui vincoli di classe di caratteri o le uguaglianze basate sulla famiglia. (Ci sono alcuni pre-processori di haskell, però, come Liquid Haskell, che ti permettono di annotare le funzioni con invarianti come questo che saranno controllati sulla compilazione.)

ci sono molte librerie haskell che offrono strutture di tipo elenco con lunghezza codificata nel tipo. Alcuni importanti sono lineare (con V) e fisso-vettore.

L'interfaccia per V più o meno così:

f :: V n a -> V n a -> V n a 
g :: V n a -> V n a -> [a] 
-- or -- 
g :: V n a -> V n a -> V ?? a -- if ?? can be determined at compile-time 

Annotare il particolare modello della nostra prima firma tipo per g: Prendiamo due tipi in cui ci stanno a cuore le lunghezze, e restituire un tipo che doesn 't cura la lunghezza, perdendo informazioni.

Nel secondo caso, se abbiamo do preoccuparsi della lunghezza del risultato, la lunghezza deve essere nota in fase di compilazione perché ciò abbia senso.

Si noti che V da lineare in realtà non racchiude un elenco, ma un vettore dalla libreria di vettori. Richiede anche l'obiettivo (la libreria lineare, cioè), che è certamente un'enorme dipendenza da inserire se tutto ciò che si desidera è un vettore con codifica della lunghezza. Penso che il tipo vettoriale da vettori fissi usi qualcosa di più equivalente ad una normale lista haskell ... ma non ne sono del tutto sicuro. In ogni caso, ha un'istanza Foldable, quindi è possibile convertirlo in un elenco.

Ricordate, naturalmente, che se avete intenzione di codificare lunghezze nelle vostre funzioni come questa ... Haskell/GHC deve essere in grado di vedere che il vostro typececk di implementazione!Per la maggior parte di queste librerie, Haskell sarà in grado di digitare tipicamente cose come questa (se si attaccano cose come zipping e fmapping, binding, ap-ping). Per la maggior parte dei casi utili questo è vero ... tuttavia, a volte la tua implementazione non può essere "dimostrata" dal compilatore, quindi dovrai "provarla" per te nella tua testa e usare una sorta di coercizione non sicura .