Funzioni polvariadiche in Haskell

Question

Dopo aver letto this article on writing polyvariadic functions in Haskell, ho provato a scrivere alcuni dei miei.

All'inizio ho pensato di provare a generalizzarlo, così avrei potuto avere una funzione che restituiva funzioni variadali comprimendo gli argomenti come dati.

{-# OPTIONS -fglasgow-exts #-} 
module Collapse where 
class Collapse a r | r -> a where 
    collapse :: (a -> a -> a) -> a -> r 
instance Collapse a a where 
    collapse _ = id 
instance (Collapse a r) => Collapse a (a -> r) where 
    collapse f a a' = collapse f (f a a') 

Tuttavia, il compilatore non piaceva che:

Collapse.hs:5:9: 
    Functional dependencies conflict between instance declarations: 
     instance Collapse a a -- Defined at Collapse.hs:5:9-20 
     instance (Collapse a r) => Collapse a (a -> r) 
     -- Defined at Collapse.hs:7:9-43 

Se sono tornato e ha aggiunto un tipo di wrapper per il risultato finale, tuttavia, ha funzionato:

module Collapse where 
class Collapse a r | r -> a where 
    collapse :: (a -> a -> a) -> a -> r 
data C a = C a 
instance Collapse a (C a) where 
    collapse _ = C . id 
instance (Collapse a r) => Collapse a (a -> r) where 
    collapse f a a' = collapse f (f a a') 
sum :: (Num a, Collapse a r) => a -> r 
sum = collapse (+) 

Una volta apportata questa modifica, è stata compilata correttamente e potrei utilizzare la funzione collapse in ghci.

ghci> let C s = Collapse.sum 1 2 3 in s 
6 

Non sono sicuro del motivo per cui il tipo di wrapper è richiesto per il risultato finale. Se qualcuno potesse spiegarlo, lo apprezzerei molto. Vedo che il compilatore mi sta dicendo che si tratta di un problema con le dipendenze funzionali, ma non ho ancora trovato l'uso corretto dei fondi.

Successivamente, ho provato a prendere una virata diversa e provare e definire un generatore di funzioni variadiche per le funzioni che hanno preso una lista e restituito un valore. Ho dovuto fare lo stesso trucco contenitore, e anche consentire UndecidableInstances.

{-# OPTIONS -fglasgow-exts #-} 
{-# LANGUAGE UndecidableInstances #-} 
module Variadic where 
class Variadic a b r | r -> a, r -> b where 
    variadic :: ([a] -> b) -> r 
data V a = V a 
instance Variadic a b (V b) where 
    variadic f = V $ f [] 
instance (Variadic a b r) => Variadic a b (a -> r) where 
    variadic f a = variadic (f . (a:)) 
list :: Variadic a [a] r => r 
list = variadic . id 
foldl :: (Variadic b a r) => (a -> b -> a) -> a -> r 
foldl f a = variadic (Prelude.foldl f a) 

Senza permettendo UndecidableInstances il compilatore lamentava che le mie dichiarazioni di istanza erano illegali:

Variadic.hs:7:0: 
    Illegal instance declaration for `Variadic a b (V b)' 
     (the Coverage Condition fails for one of the functional dependencies; 
     Use -XUndecidableInstances to permit this) 
    In the instance declaration for `Variadic a b (V b)' 

Variadic.hs:9:0: 
    Illegal instance declaration for `Variadic a b (a -> r)' 
     (the Coverage Condition fails for one of the functional dependencies; 
     Use -XUndecidableInstances to permit this) 
    In the instance declaration for `Variadic a b (a -> r)' 

Tuttavia, una volta compilato, ho potuto utilizzare con successo in ghci:

ghci> let V l = Variadic.list 1 2 3 in l 
[1,2,3] 
ghci> let vall p = Variadic.foldl (\b a -> b && (p a)) True 
ghci> :t vall 
vall :: (Variadic b Bool r) => (b -> Bool) -> r 
ghci> let V b = vall (>0) 1 2 3 in b 
True 

immagino quello che sto cercando è una spiegazione del perché è necessario il tipo di contenitore per il valore finale, nonché il motivo per cui tutte le varie funzioni le dipendenze nali sono necessarie.

Inoltre, questo sembrava strano:

ghci> let vsum = Variadic.foldl (+) 0 

<interactive>:1:10: 
    Ambiguous type variables `a', `r' in the constraint: 
     `Variadic a a r' 
     arising from a use of `Variadic.foldl' at <interactive>:1:10-29 
    Probable fix: add a type signature that fixes these type variable(s) 

<interactive>:1:10: 
    Ambiguous type variable `a'in the constraint: 
     `Num a' arising from the literal `0' at <interactive>:1:29 
    Probable fix: add a type signature that fixes these type variable(s) 
ghci> let vsum' = Variadic.foldl (+) 
ghci> :t vsum' 
(Num a, Variadic a a r) => t -> a -> r 
ghci> :t vsum' 0 
(Num a, Variadic a a r) => a -> r 
ghci> let V s = vsum' 0 1 2 3 in s 
6 

che sto indovinando che è ricaduta permettendo UndecidableInstances, ma io non lo so, e mi piacerebbe capire meglio cosa sta succedendo.

Answer 1

L'idea alla base di dipendenze funzionali è che in una dichiarazione come

class Collapse a r | r -> a where 
    ... 

il bit r -> a dice che a è determinato unicamente dalla r. Quindi, non puoi avere instance Collapse (a -> r) (a -> r) e instance Collapse a (a -> r). Si noti che instance Collapse (a -> r) (a -> r) segue da instance Collapse a a per l'immagine completa.

In altre parole, il codice sta tentando di stabilire instance Collapse t t (il nome della variabile di tipo è ovviamente non importante) e instance Collapse a (a -> r). Se si sostituisce (a -> r) per t nella dichiarazione di prima istanza, si ottiene instance Collapse (a -> r) (a -> r).Ora questa è l'unica istanza di Collapse con il secondo parametro di tipo uguale a (a -> r) che è possibile avere, perché la dichiarazione di classe indica che il primo parametro di tipo deve essere deducibile dal secondo. Successivamente, si tenta di stabilire instance a (a -> r), che aggiungerebbe un'altra istanza di Collapse con il secondo parametro di tipo (a -> r). Quindi, GHC si lamenta.

Answer 2

Michał Marczyk ha assolutamente ragione riguardo al fundep e al problema di corrispondenza dell'istanza e il tipo di wrapper sembra una soluzione semplice. D'altra parte, se stai già leggendo il sito di Oleg, potresti preferire il deeper down the rabbit hole e provare a scrivere un'istanza per "qualsiasi tipo che non sia una funzione" ".

Per quanto riguarda le condizioni Inevitabili, la condizione di copertura è descritta here; dovrebbe essere ovvio il motivo per cui le tue istanze falliscono. Si noti che la parola "indecidibile" qui significa indecidibile in circa lo stesso senso in cui "il problema dell'arresto è indecidibile" - cioè, stai dicendo a GHC di tentare incautamente di risolvere il codice che potrebbe inviarlo in un ciclo infinito basato solo sulla tua affermazione che va bene. È divertente per l'hacking di idee pulite, ma acconsentire a essere un controllore di tipo first-pass umano per GHC è un fardello che personalmente trovo stancante.

Answer 3

Se siete ancora sperimentando con questo, ecco un esempio di costruzione di una funzione polyvariadic da una funzione di prendere una lista, senza richiedere né un tipo di involucro o casi indecidibili:

{-# LANGUAGE FlexibleContexts #-} 
{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE FunctionalDependencies #-} 

class Variadic a b r | r -> a where 
    variadic :: ([a] -> b) -> r 

instance Variadic a b (a -> b) where 
    variadic f x = f [x] 

instance (Variadic a b (a -> r)) => Variadic a b (a -> a -> r) where 
    variadic f x y = variadic (f . (x:)) y 

vList :: (Variadic a [a] r) => r 
vList = variadic id 

vFoldl :: (Variadic b a r) => (a -> b -> a) -> a -> r 
vFoldl f z = variadic (foldl f z) 

vConcat :: (Variadic [a] [a] r) => r 
vConcat = vFoldl (++) [] 

main = do 
    putStrLn $ vConcat "abc" "def" "ghi" "jkl" 
    putStrLn $ vList 'x' 'y' 'z' 
    if vFoldl (&&) True True True True then putStrLn "Yes" else putStrLn "No" 
    if vFoldl (&&) True True False True then putStrLn "Yes" else putStrLn "No" 

Gli svantaggi di questo approccio è che il type checker deve essere in grado di inferire il tipo del risultato (o devi annotarlo), e che fallisce male su costanti numeriche polimorfiche; le ragioni di entrambi i problemi sono discusse nell'articolo che hai citato. Non so se lo troverai utile, ma mi sono occupato delle funzioni polivalenti prima e ho ricordato questa domanda.