Haskell: a -> a -> ... -> b per [a] -> b

Question

sto cercando di esprimere la seguente mappa come una funzione Haskell:

Dati due tipi a, b considerano la famiglia di funzioni F(a, b) costituiti funzioni del tipo

f :: a -> a -> ... -> a -> b 

con n ripetizioni di a, dove n è un numero intero maggiore di zero. Quello che voglio è quello di mappare ogni funzione f in F(a, b) a una funzione f' :: [a] -> b, in modo tale che f x1 x2 ... xr = f' [x1, ..., xr], dove r è inferiore al numero di argomenti f richiederà (vale a dire che sto cercando la funzione listify :: F(a, b) -> ([a] -> b)). Se ci sono più elementi di f accetta argomenti, gli elementi aggiuntivi devono essere eliminate:

f :: a -> a -> b 
(listify f xs) == (listify f $ take 2 xs) 

Inoltre, se l'quotata vuoto viene passato, qualsiasi valore è accettabile.

Sono ovviamente in grado di implementare questa mappa per funzioni con un numero fisso di argomenti (ad esempio: listify :: (a -> a -> b) -> ([a] -> b), ecc.), Ma non sono riuscito a trovare un modo per scrivere una funzione che lo faccia per tutti f in F(a, b) contemporaneamente. Anche se Template Haskell è probabilmente in grado di fornirmi gli strumenti giusti, non mi interessa una soluzione del genere. Voglio trovare un modo puro "tipo magico" per farlo.

Qualcuno sa se è possibile? Qualcuno può forse indicarmi la giusta direzione? O si tratta di un "problema" noto che è stato risolto miliardi di volte e non riesco a trovare una soluzione?

Answer 1

Dobbiamo solo scegliere il nostro veleno qui. Se usiamo pragmi meno sicuri, possiamo ottenere più inferenza, e viceversa; c'è un numero di combinazioni.

Prima: utilizza istanze sovrapposte, ha non funziona come caso base, ma non può gestire polimorfiche a tipi:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-} 

class Listify a b where 
    listify :: a -> b 

instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify b r where 
    listify = const 

instance (Listify f r, r ~ ([a] -> b)) => Listify (a -> f) r where 
    listify f (a:as) = listify (f a) as 

-- listify (+) [0, 2] -- error 
-- listify (+) [0, 2 :: Int] -- OK 
-- listify() [] -- OK 

Secondo: utilizza istanze sovrapposte, ha funzioni come caso base, in grado di gestire tipi polimorfici:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances, FlexibleContexts #-} 

class Listify a b where 
    listify :: a -> b 

instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify (a -> b) r where 
    listify f (a:_) = f a 

instance (Listify (a -> b) r, r ~ ([a] -> b)) => Listify (a -> a -> b) r where 
    listify f (a:as) = listify (f a) as 

-- listify (+) [0, 2] -- OK 
-- listify() [] -- error, first arg must be a function 

Terzo: usa le istanze incoerenti, ha valori in caso di base, in grado di gestire i tipi polimorfici:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-} 

class Listify a b where 
    listify :: a -> b 

instance {-# INCOHERENT #-} r ~ ([a] -> b) => Listify b r where 
    listify = const 

instance (Listify f r, r ~ ([a] -> b)) => Listify (a -> f) r where 
    listify f (a:as) = listify (f a) as 

-- listify 0 [] -- OK 
-- listify (+) [2, 4] -- OK 

Quarto: usa le famiglie tipo chiuso con UndecidableInstances come aiuto per la risoluzione di esempio, ha valori in caso di base, non può gestire tipi polimorfici:

{-# LANGUAGE UndecidableInstances, ScopedTypeVariables, DataKinds, 
    TypeFamilies, MultiParamTypeClasses, FlexibleInstances, FlexibleContexts #-} 

import Data.Proxy 

data Nat = Z | S Nat 

type family Arity f where 
    Arity (a -> b) = S (Arity b) 
    Arity b  = Z 

class Listify (n :: Nat) a b where 
    listify' :: Proxy n -> a -> b 

instance r ~ (a -> b) => Listify Z b r where 
    listify' _ = const 

instance (Listify n f r, a ~ (a' -> f), r ~ ([a'] -> b)) => Listify (S n) a r where 
    listify' _ f (a:as) = listify' (Proxy :: Proxy n) (f a) as 

listify :: forall a b. Listify (Arity a) a b => a -> b 
listify = listify' (Proxy :: Proxy (Arity a)) 

-- listify (+) [3, 4] -- error 
-- listify (+) [3, 4::Int] -- OK 
-- listify() [] -- OK 
-- listify 0 [] -- error 
-- listify (0 :: Int) [] -- OK 

Dall'alto della mia testa, approssimativamente queste sono le varianti che si possono vedere in natura, ad eccezione dello INCOHERENT, perché è estremamente raro nel codice della libreria (per buoni motivi).

Personalmente raccomando la versione con le famiglie di tipo chiuso, perché le famiglie di tipo UndecidableInstances sono di gran lunga meno controverse come estensioni di lingua e forniscono comunque una buona dose di usabilità.

Answer 2

In realtà è molto semplice, non richiede assolutamente casi si sovrappongono:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} 

class Listifiable f a b where 
    listify :: f -> [a] -> b 

instance Listifiable b a b where 
    listify = const 

instance (Listifiable f) a b => Listifiable (a->f) a b where 
    listify f (x:xs) = listify (f x) xs 

Poi si può fare

GHCi> listify ((+) :: Int->Int->Int) [1,2 :: Int] :: Int 
3 

Ma la necessità di quelle firme di tipo esplicito locali mostra abbastanza i problemi che si'

(Potrebbe essere possibile alleviare questo problema con FunctionalDependencies, ma almeno non in modo semplice.)